Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1401670 Posts in 67939 Topics- by 61482 Members - Latest Member: Domais

July 05, 2022, 08:14:03 PM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperTechnical (Moderator: ThemsAllTook)2D line / non-axis aligned rectangle collision
Pages: [1]
Print
Author Topic: 2D line / non-axis aligned rectangle collision  (Read 13907 times)
pkt-zer0
Level 0
**



View Profile
« on: February 08, 2008, 05:40:05 PM »

So, anyone know of a smart way to decide whether a line intersects a rectangle of arbitrary orientation, also acquiring the distance from the line's starting point as a result? Checking all four sides of the rectangle individually seems pretty suboptimal.

Thanks in advance.
Logged
Ishi
Pixelhead
Level 10
******


coffee&coding


View Profile WWW
« Reply #1 on: February 08, 2008, 07:11:45 PM »

That's the second time I've seen the word "suboptimal" used today. Must be a coder thing.  Grin

You can disregard the two sides facing away from the line on the other side of the rectangle (using a dot product). Then you could do line vs line tests against the two closest sides, which would probably be pretty quick.

This looks pretty nifty: http://www.angelfire.com/fl/houseofbartlett/solutions/lineinter2d.html . It doesn't give you the intersection point though so you'd have to calculate that additionally after finding out whether its collided or not. The 'ideal' solution depends how many tests you'll want to do and how many are likely to collide or not. If the majority of them will be colliding, you probably don't want to have to do the 'is it colliding' and 'where did it collide' seperately.
Logged

Wilson Saunders
Level 5
*****


Nobody suspects the hamster


View Profile WWW
« Reply #2 on: February 09, 2008, 12:55:34 AM »

Step 1 find angle between the line and the y axis
Step 2 rotate (a temporary copy of each point of the rectangle by the negative of the angle in step 1.
Step 3 If all points after rotation have a positive X value or negative X value, the line does not passes through the rectangle. If there is a mix then some of the points lie on one side of the line(now orriented on the Y axis) and the rest lie on the other, hence line passes through rectangle.
Step 4 profit
« Last Edit: February 09, 2008, 12:57:20 AM by hamster » Logged

Play my games at http://monkeydev.com/
Zaphos
Guest
« Reply #3 on: February 09, 2008, 04:02:42 AM »

Step 1 find angle between the line and the y axis
Step 2 rotate (a temporary copy of each point of the rectangle by the negative of the angle in step 1.
Step 3 If all points after rotation have a positive X value or negative X value, the line does not passes through the rectangle. If there is a mix then some of the points lie on one side of the line(now orriented on the Y axis) and the rest lie on the other, hence line passes through rectangle.
Step 4 profit
It'd be faster to use dot products here (let p be any point on the line, and v_i be the ith vertex of the rectangle; if dot_prod(p-v_0, p-v_i) < 0 for some i then the line is crossed)
But I'm guessing pkt means 'line segment,' not line?
Logged
pkt-zer0
Level 0
**



View Profile
« Reply #4 on: February 09, 2008, 05:43:39 AM »

But I'm guessing pkt means 'line segment,' not line?

Yes, I did mean line segment, sorry. Silly English words...

You can disregard the two sides facing away from the line on the other side of the rectangle (using a dot product).

Hah, never thought of using backface culling in such a situation. Cool.

Step 1 find angle between the line and the y axis
Step 2 rotate (a temporary copy of each point of the rectangle by the negative of the angle in step 1.
Step 3 If all points after rotation have a positive X value or negative X value, the line does not passes through the rectangle. If there is a mix then some of the points lie on one side of the line(now orriented on the Y axis) and the rest lie on the other, hence line passes through rectangle.
Step 4 profit

That is also a nice idea.

After some fiddling around with those two concepts and merging them, I seem to have come up with a pretty simple method that also relies much less on floating-point division than the zero-thought approach.
Logged
Ishi
Pixelhead
Level 10
******


coffee&coding


View Profile WWW
« Reply #5 on: February 09, 2008, 07:36:57 AM »

\o/

Teamwork, that was!
Logged

pkt-zer0
Level 0
**



View Profile
« Reply #6 on: February 09, 2008, 09:40:10 AM »

The code itself, for those interested (with plentiful comments, since I like to know what the heck is going on even if I haven't touched the actual code in a few months):

Code:
// Returns the distance of the intersection point from the ray's origin.
// Negative results mean no intersection.
// Fails when the origin is contained in the rectangle, test for that separately, if needed.
float intersect(Ray ray, Box box) {
Vector2D verts[5]; // array to store the vertices of the box. verts[5] = verts[1] to make things easier
box.getVerts(verts);
float sin_phi = sinf(-ray.dir);
float cos_phi = cosf(-ray.dir);

// Rotate everything so the ray is aligned with the y-axis, its x-coord is zero
ray.orig.rotateM(sin_phi,cos_phi);
float xshift = -ray.orig.r[0]; // we'll skip shifting the ray itself, x is zero, y is unaffected anyway
for (int i=0; i<4; ++i) {
verts[i].rotateM(sin_phi,cos_phi);
verts[i].r[0] += xshift;
}
verts[4] = verts[0]; // makes the next loop simpler
for (int i=0; i<4; ++i) {
if ((verts[i].x() < 0) && (verts[i+1].x() >= 0)) { // intersection
Vector2D diff = verts[i+1] - verts[i];
return verts[i].y() - diff.y()/diff.x() * verts[i].x() - ray.orig.y();
}
}
// Why the above if() works:
// - the ray's direction vector is (0,1), so the sides facing the ray have a normal vector with n.y < 0
// - the vertices are in CCW order, so the normal of an edge will be (d.y,-d.x), where d = v[i+1] - v[i]
// - substituting into n.y < 0 we get v[i].x - v[i+1].x < 0, which is v[i].x < v[i+1].x
// - thus, we are only interested in the edges going left to right, so we needn't test for the opposite case
return -1;
}

\o/ indeed. Thanks, all of you.
Logged
r.kachowski
Level 5
*****

and certainly no love below


View Profile WWW
« Reply #7 on: February 14, 2009, 10:16:46 AM »

over one year has passed since these events...

Actually I have the exact same problem, I've searched google for a while and coincidentally the closest match turns out to be on tigforums  Shrug

I want to find a collision between a line and an obb, I don't care about finding the point in the line that collides.

I tried following the advice in this thread, but I must have horribly misunderstood something.

Here's my collision method:
Code:
         bool lineRectangleCollision(Vector2 linepoint1, Vector2 linepoint2,
            Rectangle hitBox)
        {

            #region get rectangle verts
            List<Vector2> recVerts = new List<Vector2>(4);

            recVerts.Add(new Vector2(hitBox.X, hitBox.Y));
            recVerts.Add(new Vector2(hitBox.X, hitBox.Y + hitBox.Height));
            recVerts.Add(new Vector2(hitBox.X + hitBox.Width, hitBox.Y + hitBox.Height));
            recVerts.Add(new Vector2(hitBox.X + hitBox.Width, hitBox.Y));
            #endregion           

            Vector2 line = linepoint2 - linepoint1;

            line.Normalize();

            //find angle between y axis and line
            float angle =
                (float)Math.Acos(
                Vector2.Dot( line, (Vector2.UnitY) ));


            Console.WriteLine(MathHelper.ToDegrees(angle));

            if (linepoint2.X > linepoint1.X)
            {
                angle = -angle;
            }
               Matrix rotation = Matrix.CreateTranslation(new Vector3(linepoint2, 0f)) *
                Matrix.CreateRotationZ(angle);

            for(int i =0;i<4;i++)
            {
                recVerts[i] = Vector2.Transform(recVerts[i], rotation);

            }

            //return false if any values are not a number
            if (recVerts.Any(CheckIfNaN))
            {
                return false;
            }

            //if allpoints are positive or negative
            if (recVerts.All(CheckIfXPositive) || recVerts.All(CheckIfXNegative))
            {
                return false;
            }
            else
            {

                //any mix of the 2 is a collision
                Console.WriteLine("hit");
                foreach (Vector2 vec in recVerts)
                {
                    Console.WriteLine(vec);
                }
                return true;
            }

Could someone help a tigger out and show him some love this valentines day?  Beg
show me the error of my noobish ways
« Last Edit: February 19, 2009, 08:14:11 AM by qrrbrbirlbel » Logged
r.kachowski
Level 5
*****

and certainly no love below


View Profile WWW
« Reply #8 on: February 19, 2009, 11:35:59 AM »

So I spent valentines day with a bottle of scotch and a book on vector algebra  Tired Noir

It turns out my love letter to matrix multiplication got lost in the post. Being the fickle mistress she is, she upped left me for a career in projection. In my drunken stupor I smashed everything we'd made together, everything that reminded me of her.

"Fuck your rotations! I'm going back to AABB!!", I said as I ripped all traces of orientation from both my mind and the depths of EnemyManager.cs. Intellisense screaming in agony, throwing up red pools of unreturned code paths and compiler warnings.

I blazed on through the night, cursing the moment she waltzed into my design. With sugar sweet promises of elegant collision detection and efficiency she blew my world. "Sweep and pruneWink" she said.

Nothing mattered, now that she'd left me what use was a two-bit data structure, lingering on in the back of my method, declared but not assigned...

Waking up blearily the next day, my fingers trembled toward F5 to see what damage had been done. My mind jarred, thinking about all the times we'd spent debugging on the coffee table. Dubious substances cast aside as we dropped breakpoints together into the small hours of morning, she was my everything.

Turns out it worked fine  Beer! I used Ishi's method. Guess rotations are out of my league for now :D

Here's my implementation in c#/xna

Code:
        public enum LineClockDir
        {
            Clockwise,
            CClockwise,
            Line
        }

        LineClockDir getClockPosition(Vector2 pt1, Vector2 pt2, Vector2 pt3)
        {
            float tester = ( ((pt2.X - pt1.X) * (pt3.Y - pt1.Y)) - ((pt3.X - pt1.X) * (pt2.Y - pt1.Y)) );

            if (tester > 0)
                return LineClockDir.CClockwise;
            else if (tester < 0)
                return LineClockDir.Clockwise;
            else
                return LineClockDir.Line;

        }

        bool lineLineCollision(Vector2 l1p1, Vector2 l1p2, Vector2 l2p1, Vector2 l2p2)
        {
            LineClockDir test1a, test1b, test2a, test2b;

           
            test1a = getClockPosition(l1p1, l1p2, l2p1);
            test1b = getClockPosition(l1p1, l1p2, l2p2);

            if (test1a != test1b)
            {

                test2a = getClockPosition(l2p1, l2p2, l1p1);
                test2b = getClockPosition(l2p1, l2p2, l1p2);
               
                if (test2a != test2b)
                {
                    return true;
                }
            }

            return false;
        }

        bool lineRectangleCollision(Vector2 linepoint1, Vector2 linepoint2,
            Rectangle hitBox)
        {

            #region get rectangle verts
            List<Vector2> recVerts = new List<Vector2>(4);

            recVerts.Add(new Vector2(hitBox.X, hitBox.Y));
            recVerts.Add(new Vector2(hitBox.X, hitBox.Y + hitBox.Height));
            recVerts.Add(new Vector2(hitBox.X + hitBox.Width, hitBox.Y + hitBox.Height));
            recVerts.Add(new Vector2(hitBox.X + hitBox.Width, hitBox.Y));
            #endregion           

            if (
                //testing left side of rectangle
             lineLineCollision(linepoint1, linepoint2, recVerts[0], recVerts[1])
                ||
                //testing top side
             lineLineCollision(linepoint1, linepoint2, recVerts[0], recVerts[3])
                ||
                //testing right side
             lineLineCollision(linepoint1, linepoint2, recVerts[3], recVerts[2])
                ||
                //testing bottom
             lineLineCollision(linepoint1, linepoint2, recVerts[1], recVerts[2]))
            {
                return true;
            }
            else
                return false;
           
        }

It's probably horribly inefficient, but it's not like I'm losing frames all over the place.
Logged
Ivan
Owl Country
Level 10
*


alright, let's see what we can see


View Profile
« Reply #9 on: February 19, 2009, 12:32:41 PM »

http://www.gamedev.net/reference/programming/features/2dRotatedRectCollision/
Logged

http://polycode.org/ - Free, cross-platform, open-source engine.
Greg
Level 0
***


has a compass, lost my map


View Profile
« Reply #10 on: February 19, 2009, 03:09:16 PM »

From my understanding, the Separating Axis Theorem is the one used for collision between two OBBs.  I implemented it once from this article: http://www.gamasutra.com/features/19991018/Gomez_5.htm and the one above^.  A bit overkill for line+OBB intersection though.
Logged

A day for firm decisions!!! Or is it?
Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic