next »

[pkt-zer0]

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.

[Ishi]

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

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.

[Wilson Saunders]

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

[Zaphos]

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?

[pkt-zer0]

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.

[Ishi]

\o/

Teamwork, that was!

[pkt-zer0]

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.

[r.kachowski]

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 

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? 
show me the error of my noobish ways

[r.kachowski]

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

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 prune" 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  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.

[Ivan]

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

[Greg]

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.