Archived

This topic is now archived and is closed to further replies.

ProblemBaby

Check if a Rectangle and a Line collide

Recommended Posts

i cant remember the forumale, but you can work out if two lines intersect, so basically u check all 5 lines.

you get the equation of the line, and do something with it or so, use google or someting

its fairly simple, and probably the clearest way,

and it wont matter if the lines are straight or not

edit
oh and to work out the collision point would be

eg
3y=2x+5 ...(1)
y=3x-3 ...(2)

then

5= 3y - 2x ...(3)
3 =y-3x ...(4)

then
...(4) * 3
12 = 3y - 9x ...(5)

then
(3)-(5)

5= 3y - 2x ...(3)
12 = 3y - 9x ...(5)
-7=5x
x=-7/5

SO now u have found the x pos
then

sub x=-7/5 into (2)

y= 3*(-7/5)-3


so
x=-7/5
y= 3*(-7/5)-3

im 2 lazy to work out the numbers, but its pretty simple,












[edited by - johnnyBravo on November 16, 2003 9:21:58 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Leyder Dylan
http://www.gametutorials.com/

========================
Leyder Dylan (dylan.leyder@slug-production.be.tf
http://users.skynet.be/fa550206/Slug-Production/Index.htm/

WOW, you have been around these forums for three years but you still don''t know how to use hyperlinks! Or maybe you don''t want to use them?!

Share this post


Link to post
Share on other sites
if p1 and p2 give you the line:


vNormal.x = -(p1 - p2).y;
vNormal.y = (p1 - p2).x;

float d;
float center;

for (i = 0; i < numVertices; i++)
objectCenter += vertices[i];

objectCenter /= numVertices;

center = DotProd(p1 - objectCenter, vNormal);

for (i = 0; i < numVertices; i++)
{
d = DotProd(p1 - vertices[i], vNormal);

if (d * center < 0) BANG Collision!
}


[edited by - Ilici on November 16, 2003 9:27:00 AM]

Share this post


Link to post
Share on other sites
Excellent. This is exactly what I was going to ask!

Ilici: I tried your method, but, unless I am doing something wrong, it seems HIGHLY inaccurate. I created a fast and short C# demo (1.0 Framework). It's pretty much the code you posted but instead of testing between a line and a polygon, I modified the code to test between a line and a rectangle. I would appreciate if you or anyone else could take a look and verify it.

C# test


gametutorials.com doesn't have very much on it and nothing as far as this is concerned. Or at least I couldn't find anything.

johnnyBravo: I'll try your method next. It seems the most promising if Ilici's method doesn't work that well.

[edited by - JasonA on November 16, 2003 7:04:14 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by JasonA
Excellent. This is exactly what I was going to ask!

Ilici: I tried your method, but, unless I am doing something wrong, it seems HIGHLY inaccurate. I created a fast and short C# demo (1.0 Framework). It''s pretty much the code you posted but instead of testing between a line and a polygon, I modified the code to test between a line and a rectangle. I would appreciate if you or anyone else could take a look and verify it.

C# test





well, i''ve used it and it was very good. basiclly it tests if each of the vertices are on the same side of the line. the dot product is > 0 if they 2 points are on the same side and < 0 if the points are on different sides.

Share this post


Link to post
Share on other sites
its a nice first step, but you need the point of intersection to check if this point is even part of the rectangle side.

your life will be a lot easier if the rectangles are axis aligned, maybe even so much easier that i would think about transforming line and rectangle to make it axis aligned.

after that for the left side:
if (side.y-p0.y)*(side.y-p1.y) is positive both points (start and end point of your line) are on the same side of the side (the same as above with the dot product, just simpler). in that case, go to the next side.

if its negative or 0 you line equation looks like this:
p0 + t*(p1-p0). you know it will intersect, so:
p0.y + t*(p1.y-p0.y) = side.y

solving this shouldnt be hard and you get a t.

short:
t = (side.y - p0.y) / (p1.y - p0.y)

if this t is smaller than 0 or larger than 1 they would intersect, but not in the interval between p0 and p1 (though here they will, we already did a quick and dirty test to figure that out). but the equation for our simplified 2d case is easy enough so forget about the quick and dirty test ,-)

next, plug this t into the equation to get x at the intersection.
x = p0.x + t * (p1.x-p0.x)

this x has to be between the two points of the rectangle side:
if xside.maxx forget it and go to the next side.

also, you might get up to 4 intersections but the one with the smallest t will happen first.

doing the same without the rectangle being axis aligned isnt much different except you would have line equations on both sides and solving this will be a little more work.

p0 + t*(p1-p0) = side0 + s*(side1-side0)

basically twice, for x and y coord. solve one for s and then plug the whole ugly thing into the other instead of s, then solve for t. chances are that a lot of sites will already present you with the formula ,-)

in the end both, s and t will have to be between 0 and 1 for the segments to intersect, if you need the point of intersection just plug t or s into its equation.

[edited by - Trienco on November 18, 2003 12:52:30 PM]

Share this post


Link to post
Share on other sites
separation axis, or rectangle clipping, the choice is yours.

The separation axis is faster, but does not tell you anything about how the line/rect collided. The clipping algorithm is slower, but returns the part of the segment inside the cube.

class Box
{
Vector2 Dir[2]; //the orientation of the box (for AABBox, Dir[0] = (1, 0), Dir[1] = (0, 1)
float HalfSize[2]; // the extents of the box along Dir[0] and Dir[1]
};

class Segment
{
Vector2 P1, P2;
};

separation axis
---------------


void Segment::GetSpan(const Vector2& Axis, float& min, float& max) const
{
float p1 = this->P1 * Axis;
float p2 = this->P2 * Axis;

if (p1 < p2)
{
min = p1;
max = p2;
}
else
{
min = p2;
max = p1;
}
}

void Box::GetSpan(const Vector2& Axis, float& min, float& max) const
{
float c = Centre * Axis;
float r = fabs(Axis * Dir[0]) * HalfSize[0] + fabs(Axis * Dir[1]) * HalfSize[1];
min = c - r;
max = c + r;
}
bool Box::AxisIntersect(const Vector2& Axis, const Segment& S) const
{
float mins, maxs;
float minb, maxb;
this->GetSpan(Axis, minb, maxb);
S.GetSpan(Axis, mins, maxs);

if (mins > maxb || maxs < minb)
return false;
return true;
}

bool Box::Intersect(const Segment& S) const
{
Vector2 Dir = S.P2 - S.P1;
if (!AxisIntersect(Dir, S})
return false;

if (!AxisIntersect(Vector2(-Dir.y, Dir.x), S})
return false;

if (!AxisIntersect(Dir[0], S})
return false;

if (!AxisIntersect(Dir[1], S})
return false;

return true;
}


clipping
--------



static bool AxisClip(float min, float max, float p1, float p2, float &tmin, float& tmin)
{
float d = p2 - p1;

bool sign = (d > 0.0f);

if (!sign)
{
float temp = p1;
p1 = p2;
p2 = temp;
d = -d;
}
if (p1 > max || p2 < min)
return false;

tmin = 0.0f;
tmax = 1.0f;

if (d < 0.0000001f)
return true;

if (p1 < min)
tmin = (min - p1) / (d);

if (p2 > max)
tmax = (max - p1) / (d);

if (!sign)
{
float temp = p1;
p1 = 1.0f - p2;
p2 = 1.0f - temp;
}
return true;
}

bool Segment::Clip(const AABBox& B, Segment& ClippedSeg) const
{
float minx, maxx;
float miny, maxy;

if (!AxisClip(B.MinX, B.MaxX, P1.x, P2.x, minx, maxx))
return false;

if (!AxisClip(B.MinY, B.MaxY, P1.y, P2.y, miny, maxy))
return false;

if (minx > maxy || maxx < miny)
return false;

float tmin, tmax;
tmin = minx;
tmax = maxx;

if(miny > minx)
tmin = miny;

if(maxy < maxx)
tmax = maxy;

Vector2 D = P2 - P1;
ClippedSeg.P1 = P1 + tmin * D;
ClippedSeg.P2 = P1 + tmax * D;

return true;
}



I''ll explain everything tomorrow... bedtime and the land of nod

Share this post


Link to post
Share on other sites
the line clipping algo is basicaly what trienco said, except I do two parallel edges at a time. Why you may ask? here is why



// intersecting

//-------------

xmin xmax
P1 | |
* | |
\ | | ymax
--.-+-----+-----
ty0\| |
.tx0 | ymin
----+.----+-----
| \ty1|
| \ |
| \ |
| \|
| .tx1
| |*P2



// here the spans [tx0, tx1 and ty0, ty1] overlap, so the ray

// crosses the rectangle

// furthermore, the ray is clipped to [tx0, ty1]





// non-intersecting

//-----------------


xmin xmax
| |
*P1 | |
\ ty0 | | ymax
--.-----+-----+-----
\ | |
\ ty1 | ymin
------.--+-----+-----
\ | |
\| |
.tx0 |
|\ |
| \ |
| \ |
| \ |
| \|
| . tx1
| |\
| | *P2


// here the spans [tx0, tx1] and [ty0, ty1] do not overlap (ty1 < tx0). So the segment does not clipp the rectangle.



it''s a typical way to intersect a ray with a box/rectangle. It''s quite fast. For oriented boxes, as trienco said, you can rotate the segment with the opposite angle of the rectangle (or the inverse of the orientation matrix of the rectangle), clip the segment with the Axis aligned box, and re-rotate the clipped segment with the rectangle''s angle.

Or you can do the test with proper slopped segments, which isn''t hard.


there you go anyway...




static bool AxisClip(float min, float max, float p1, float p2, float &tmin, float& tmin)
{
float d = p2 - p1;

bool sign = (d > 0.0f);

if (!sign)
{
float temp = p1;
p1 = p2;
p2 = temp;
d = -d;
}

if (p1 > max || p2 < min)
return false;

tmin = 0.0f;
tmax = 1.0f;

if (d < 0.0000001f)
return true;

if (p1 < min)
tmin = (min - p1) / (d);

if (p2 > max)
tmax = (max - p1) / (d);

if (!sign)
{
float temp = p1;
p1 = 1.0f - p2;
p2 = 1.0f - temp;
}
return true;
}

bool Segment::BoxAxisClip(const Vector2& C, const Vector2& D, float r, float &tmin, float& tmin) const
{
float c = C * D;
float p1 = P1 * D;
float p2 = P2 * D;
return AxisClip(c-r, c+r, p1, p2, tmin, tmax);
}

bool Segment::Clip(const AABBox& B, Segment& ClippedSeg) const
{
float minx, maxx;
float miny, maxy;

if (!AxisClip(B.MinX, B.MaxX, P1.x, P2.x, minx, maxx))
return false;

if (!AxisClip(B.MinY, B.MaxY, P1.y, P2.y, miny, maxy))
return false;

if (minx > maxy || maxx < miny)
return false;

float tmin, tmax;
tmin = minx;
tmax = maxx;

if(miny > minx)
tmin = miny;

if(maxy < maxx)
tmax = maxy;

Vector2 D = P2 - P1;
ClippedSeg.P1 = P1 + tmin * D;
ClippedSeg.P2 = P1 + tmax * D;

return true;
}

bool Segment::Clip(const Box& B, Segment& ClippedSeg) const
{
float minx, maxx;
float miny, maxy;
if (!BoxAxisClip(Box.Centre, Box.Dir[0], Box.HalfSize[0], minx, maxx))
return false;

if (!BoxAxisClip(Box.Centre, Box.Dir[1], Box.HalfSize[1], miny, maxy))
return false;

if (minx > maxy || maxx < miny)
return false;

float tmin, tmax;
tmin = minx;
tmax = maxx;

if(miny > minx)
tmin = miny;

if(maxy < maxx)
tmax = maxy;

Vector2 D = P2 - P1;
ClippedSeg.P1 = P1 + tmin * D;
ClippedSeg.P2 = P1 + tmax * D;

return true;
}

Share this post


Link to post
Share on other sites