2d Ray intersection

Question

I've recently picked up a class which creates 2D Rays and detects if the ray is intersecting any bounding boxes passed through it.

public struct Ray2D
    {
        private Vector2 startPos;
        private Vector2 endPos;
        private readonly List<Point> result;

        public Ray2D(Vector2 startPos, Vector2 endPos)
        {
            this.startPos = startPos;
            this.endPos = endPos;
            result = new List<Point>();
        }

        /// <summary>  
        /// Determine if the ray intersects the rectangle  
        /// </summary>  
        /// <param name="rectangle">Rectangle to check</param>  
        /// <returns></returns>
        /// 
        public Vector2 Intersects(Rectangle rectangle)
        {
            Point p0 = new Point((int)startPos.X, (int)startPos.Y);
            Point p1 = new Point((int)endPos.X, (int)endPos.Y);

            foreach (Point testPoint in BresenhamLine(p0, p1))
            {
                if (rectangle.Contains(testPoint))
                    return new Vector2((float)testPoint.X, (float)testPoint.Y);
            }
            return Vector2.Zero;
        }

        // Swap the values of A and B  

        private void Swap<T>(ref T a, ref T b)
        {
            T c = a;
            a = b;
            b = c;
        }

        // Returns the list of points from p0 to p1   

        private List<Point> BresenhamLine(Point p0, Point p1)
        {
            return BresenhamLine(p0.X, p0.Y, p1.X, p1.Y);
        }

         // Returns the list of points from (x0, y0) to (x1, y1)  

        private List<Point> BresenhamLine(int x0, int y0, int x1, int y1) 
        { 
            // Optimization: it would be preferable to calculate in  
            // advance the size of "result" and to use a fixed-size array  
            // instead of a list.  

            result.Clear(); 

            bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); 
            if (steep) 
            { 
                Swap(ref x0, ref y0); 
                Swap(ref x1, ref y1); 
            } 
            if (x0 > x1) 
            { 
                Swap(ref x0, ref x1); 
                Swap(ref y0, ref y1); 
            } 

            int deltax = x1 - x0; 
            int deltay = Math.Abs(y1 - y0); 
            int error = 0; 
            int ystep; 
            int y = y0; 
            if (y0 < y1) ystep = 1; else ystep = -1; 
            for (int x = x0; x <= x1; x++) 
            { 
                if (steep) result.Add(new Point(y, x)); 
                else result.Add(new Point(x, y)); 
                error += deltay; 
                if (2 * error >= deltax) 
                { 
                    y += ystep; 
                    error -= deltax; 
                } 
            } 

            return result; 
        } 
    }

Based off this class I'm cycling through every tile in the level to determine if the ray has indeed intersected with any of the boxes and then move on from there

camToChar = new Ray2D(lensPosition, level.Player.Position);   
            // For each potentially colliding tile,
            for (int y = tileMap.GetHeight(); y <= tileMap.GetHeight(); ++y)
            {
                for (int x = tileMap.GetWidth(); x <= tileMap.GetWidth(); ++x)
                {
                    TileCollision collision = Level.GetCollision(x, y, tileMap);
                    if (collision != TileCollision.Passable)
                    {
                        // Determine collision depth (with direction) and magnitude.
                        Rectangle tileBounds = Level.GetBounds(x, y);

                        Vector2 depth = camToChar.Intersects(tileBounds);

                        if (depth != Vector2.Zero)
                        {
                            clockwise = true;
                        }
                    }
                }
            }

The problem is that despite the fact the ray should be passing through bounding boxes, the intersect method never gives this result. I'm trying to determine if it is an issue with either the 2DRay class or the way I've constructed method to use it.

Any help with this would be greatly appreciated.

Answer 1

There may be a bug in this line:

for (int y = tileMap.GetHeight(); y <= tileMap.GetHeight(); ++y)

Maybe it should have been:

for (int y = 0; y < tileMap.GetHeight(); ++y)

Answer 2

Bresenham line algorithm is not intended to collision detection tests. It is intended to discretize and achieve an aproximation to draw lines on the screen. With bresenham accuracy is being lost.

To collision tests you can use geometric equations. In this case the bounding box can be separated in four segments and check if any of the segments intersects with the ray ( other segment ).

I write you a code to this test in C++, sorry but I'm not familiarized with C# but the conversion must be very easy.

float signedTriangleArea( const vector2df& pointA,
                          const vector2df& pointB,
                          const vector2df& pointC
                        )
{
    return ( pointA.X - pointC.X ) * ( pointC.Y - pointB.Y ) - ( pointC.Y - pointA.Y ) * ( pointB.X - pointC.X );
}

bool testSegmentsIntersection( const vector2df& pointA,
                               const vector2df& pointB,
                               const vector2df& pointC,
                               const vector2df& pointD 
                             )
{
    float a1 = signedTriangleArea( pointA, pointB, pointD );
    float a2 = signedTriangleArea( pointA, pointB, pointC );

    if ( a1 * a2 < 0.f )
    {
        float a3 = signedTriangleArea( pointC, pointD, pointA );
        float a4 = a3 + a2 - a1;

        if ( a3 * a4 < 0.f )
            return true;

        return false;
   }

The triangle area is useful because the sign of the function can determine if a point is on the left or on the right of a segment.

Answer 3

Another alternative is to use XNA's built in Ray class and BoundingBox class. Although they are typically used in 3d, often (as in this case) you can simply set their Z components to zero and utilize them in 2d as needed. It seems to me that that would achieve a dramatic simplification to your code.