2
\$\begingroup\$

I'm writing some code to check intersection between all of a rectangles segments and a ray. It will sometimes use the Left and Right side of the rectangle as the closest face hit (face DA & BC) even when it is clearly on the top of the rectangle (face AB).

This is what the Rectangle v Ray collision looks like.

    // Ray intersections
    static public IntersectData IntersectRectRay(Rectanglef rect, Vector2 origin, float dir)
    {
        IntersectData data = new IntersectData();

        // Create segments for all the sides of a rectangle
        Segment topLeftRight = new Segment(rect.TopLeft, rect.TopRight);
        Segment leftTopBottom = new Segment(rect.TopLeft, rect.BottomLeft);
        Segment bottomLeftRight = new Segment(rect.BottomLeft, rect.BottomRight);
        Segment rightTopBottom = new Segment(rect.TopRight, rect.BottomRight);

        // Check collision with all the faces and use the closet one
        float smallestDepth = float.PositiveInfinity;

        IntersectData topLeftRightData = IntersectSegmentRay(topLeftRight, origin, dir);
        if (topLeftRightData.intersecting && topLeftRightData.depth.Length() < smallestDepth)
        {
            smallestDepth = topLeftRightData.depth.Length();
            data = topLeftRightData;
            data.face = "AB";
            data.dir = MathHelper.PI / 2f;
        }

        IntersectData leftTopBottomData = IntersectSegmentRay(leftTopBottom, origin, dir);
        if (leftTopBottomData.intersecting && leftTopBottomData.depth.Length() < smallestDepth)
        {
            smallestDepth = leftTopBottomData.depth.Length();
            data = leftTopBottomData;
            data.face = "DA";
            data.dir = 0f;
        }

        IntersectData bottomLeftRightData = IntersectSegmentRay(bottomLeftRight, origin, dir);
        if (bottomLeftRightData.intersecting && bottomLeftRightData.depth.Length() < smallestDepth)
        {
            smallestDepth = bottomLeftRightData.depth.Length();
            data = bottomLeftRightData;
            data.face = "CD";
            data.dir = MathHelper.PI / 2f;
        }

        IntersectData rightTopBottomData = IntersectSegmentRay(rightTopBottom, origin, dir);
        if (rightTopBottomData.intersecting && rightTopBottomData.depth.Length() < smallestDepth)
        {
            data = rightTopBottomData;
            data.face = "BC";
            data.dir = 0f;
        }

        return data;
    }

and this is the ray v Segment intersection

    static public IntersectData IntersectSegmentRay(Segment seg, Vector2 origin, float dir)
    {
        IntersectData data = new IntersectData();

        // Get vector between p1 and p2
        Vector2 q = seg.p1;
        Vector2 s = seg.p2 - seg.p1;
        Vector2 p = origin;
        Vector2 r = new Vector2((float)Math.Cos(dir), (float)Math.Sin(dir)) * 100000f;

        float t = MathHelper.Vec2CrossProduct(q - p, s) / MathHelper.Vec2CrossProduct(r, s);
        float u = MathHelper.Vec2CrossProduct(q - p, r) / MathHelper.Vec2CrossProduct(r, s);

        if (MathHelper.Vec2CrossProduct(r, s) != 0 && t <= 1 && t >= 0 && u <= 1 && u >= 0)
        {
            data.intersecting = true;
            data.depth = p + t * r;//q + u * s;
            data.dir = dir;
        }

        return data;
    }

Extra Info: My Vec2CrossProduct is V × W to be Vx Wy − Vy Wx

I imagine there is something wrong with the ray segment intersection because if I tried to replace that 100000f with float.PositiveInfinity() it won't work.

\$\endgroup\$
1

2 Answers 2

3
\$\begingroup\$

Well a simple ray vs line segment intersection is:

function RayToLineSegment(x, y, dx, dy, x1, y1, x2, y2)
{
    var r, s, d;
    //Make sure the lines aren't parallel, can use an epsilon here instead
    // Division by zero in C# at run-time is infinity. In JS it's NaN
    if (dy / dx != (y2 - y1) / (x2 - x1))
    {
        d = ((dx * (y2 - y1)) - dy * (x2 - x1));
        if (d != 0)
        {
            r = (((y - y1) * (x2 - x1)) - (x - x1) * (y2 - y1)) / d;
            s = (((y - y1) * dx) - (x - x1) * dy) / d;
            if (r >= 0 && s >= 0 && s <= 1)
            {
                return { x: x + r * dx, y: y + r * dy };
            }
        }
    }
    return null;
}

That said a ray to rectangle aka axis-aligned boundary box (AABB) can be done without doing a normal ray vs line segment check since the line segments are all horizontal or vertical you end up with a very simple algorithm: most efficient AABB vs Ray collision algorithms

\$\endgroup\$
8
  • \$\begingroup\$ Is there a more etficient OBB v Ray algorithm? Or is it easier to use segments? \$\endgroup\$ Oct 8, 2015 at 20:11
  • 2
    \$\begingroup\$ You can rotate the ray and direction around the OBB (inverse of the rectangle's rotation) such that the OBB can be treated like an AABB. \$\endgroup\$
    – Sirisian
    Oct 8, 2015 at 20:16
  • \$\begingroup\$ -1 this solution will crash the program for dx = 0 or x2 - x1 = 0. I suggest using more stable implementation (will undo when fixed). \$\endgroup\$
    – wondra
    Oct 8, 2015 at 22:20
  • \$\begingroup\$ I made a change, but reverted it. In C# at run-time 1/0 is infinity. It's stable. Added a comment to help anyone converting to another language. \$\endgroup\$
    – Sirisian
    Oct 8, 2015 at 23:45
  • 2
    \$\begingroup\$ It's not an error. Division by zero is well defined. Please refer to the spec of your target language. This question is about C# using floats. I'm not going to add code examples for every language and data type. If you want to be pedantic create your own answer. \$\endgroup\$
    – Sirisian
    Oct 9, 2015 at 19:49
0
\$\begingroup\$

thanks to Sirisian wrote, i adopted it a bit to my code for proximity sensor for neural network:

// convenient mapping for neural network distance sensor;
scalar get_distance_inverse_squared(const point& qp, const point& d, const segment& s)  {
    auto s0s1 = s[1] - s[0];
    auto s0qp = qp - s[0];
    auto dd = d[0] * s0s1[1] - d[1] * s0s1[0];
    if (dd != 0) {
        auto r = (s0qp[1] * s0s1[0] - s0qp[0] * s0s1[1]) / dd;
        auto s = (s0qp[1] * d[0] - s0qp[0] * d[1]) / dd;
        if (r >= 0 && s >= 0 && s <= 1) {
            // linear inverse of distance, always less than 1.0
            return scalar(1) / (r + 1);
        }
    }
    return 0; // infinitely far, parallel, etc, no signal
}
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .