lol

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

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; }