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\$
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\$
  • \$\begingroup\$ Is there a more etficient OBB v Ray algorithm? Or is it easier to use segments? \$\endgroup\$ – Andrew Wilson Oct 8 '15 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 '15 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 '15 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 '15 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 '15 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.