• Advertisement
Sign in to follow this  

Fastest code of 2D line intersected with rectangle

This topic is 3868 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi All i am looking for the Fastest code of 2D line intersected with rectangle , and specify the intersected point. any help please?

Share this post


Link to post
Share on other sites
Advertisement
I just check my line against each line of the box's edges, eliminate the points not on the box, then pick the closest point to what I want. I don't know if it's the absolute fastest way, but for an axis aligned rectangle it's a very simple calculation. I suspect if your line is actually a ray you could do a comparison before the collission and then only have to check the two sides of the box closest to your ray origin.

Share this post


Link to post
Share on other sites
A method that is commonly used (and that may, generally speaking, be the fastest) is the 'clipping' method, where the line is clipped against the bounding hyperplanes of the polytope in sequence. If at any point the line is completely clipped away, there is no intersection; otherwise, the intersection points are the endpoints of the clipped line.

Needless to say, this can be optimized quite well for boxes (whether axis-aligned or oriented).

The details of how to do this have been discussed countless times on these forums, but if you get stuck, post back (I've probably got some code lying around that I could post, as do others, I'm sure).

Share this post


Link to post
Share on other sites
thanks Alrecenk , jyk .

I have searched for 'clipping' method of line intersection , and got many topics but I really did not find my needs , so please jyk could you point me to a specific tutorial or post your code.

Share this post


Link to post
Share on other sites
Quote:
Original post by Emil_Halim

Hi All

i am looking for the Fastest code of 2D line intersected with rectangle , and specify the intersected point.

any help please?


You won't get anything faster than this:

bool BoxLineIntersection (const Box &box, const Line &line)
{
return false;
}

OK, it's not very useful, but if you were to analyse the results of proper clipping, you'd find the above was at least 90% accurate. What I'm saying is that not doing something will always be faster than doing something and rather than optimising the function which is being called many times, try reducing the number of calls to the function.

The box-line instersection is computationally heavy, so it would be a good idea to find a trivial rejection method. Fortunately, circle-line is computationally light, especially if all you're interested in is whether the line intersects or not1.

Remember that optimising code on PCs is no easy task because of the shear number of permutations of CPU type, cache sizes, bus speeds and so on. What works fast on your PC may be quite slow on another. And never forget to profile the results.

Skizz

(1) In case you're wondering how to do this, the line intersects the circle and thus possibly intersects the box if:

square of distance from point at centre of smallest bounding circle of box to the line < square of half the diagonal of box




Share this post


Link to post
Share on other sites
Skizz , your idea is very good but first see the next Picture and let me know what do you mean by smallest bounding circle of box , is it the first pic or the second one ?

http://bcxdx.spoilerspace.com/test.GIF

So , I think using circle instead rectangle as you already said is faster but is not 100% accurate.

Another thing is there any one has a clip method of line interested with rectangle ?

Share this post


Link to post
Share on other sites
Quote:
Original post by Emil_Halim
Skizz , your idea is very good but first see the next Picture and let me know what do you mean by smallest bounding circle of box , is it the first pic or the second one ?




The first pic is not a bounding circle of the box.

Share this post


Link to post
Share on other sites
Quote:
Original post by Emil_Halim

So , I think using circle instead rectangle as you already said is faster but is not 100% accurate.


It's not designed to be 100% accurate with regard to intersecting the box. It is only designed to quickly reject lines that definately don't intersect the box. If the line intersects the circle, then, and only then, try the line-box test.

Skizz

Share this post


Link to post
Share on other sites

thanks ToohrVyk , Skizz.

ok that is good , first check the Circle-Line intersected and if so check for line - line intersected for each line in the rectangle.

So where can i find an optimized line - line intersected code ?

Share this post


Link to post
Share on other sites
a quickie, jyk's method (and my choice too).



bool AxisIntersect(float s, float e, foat min, float max, float& t_enter, float& t_exit)
{
float d = (e - s);
if (fabs(d) < 0.000001)
{
return (s > min && s < max);
}
float invd = 1.0f / d;
float t0 = (min - s) * invd;
float t1 = (max - s) * invd;
if(t1 < t0)
{
float temp = t0;
t0 = t1;
t1 = temp;
}

if (t0 > t_exit || t1 < t_enter)
return false;

if(t0 > t_enter) t_enter = t0;
if(t1 < t_exit) t_exit = t1;
return true;
}

bool intersectSegmentRectangle(const Vector& start, const Vector& end, const Vector& min, const Vector& max, float &t)
{
float t_enter = 0.0f;
float t_exit = 1.0f;

if (!AxisIntersect(start.x, end.x, min.x, max.x, t_enter, t_exit)) return false;
if (!AxisIntersect(start.y, end.y, min.y, max.y, t_enter, t_exit)) return false;

t = t_enter;

return true;
}



for 3D, simply add the 'z' case.

if you test your segement against many boxes, you can save yourself a division.

float d = (e - s);
float invd = 1.0f / d;

that part remains constant as long as the ray remains unchanged. So you can do



bool AxisIntersect(float s, float invd, foat min, float max, float& t_enter, float& t_exit)
{
if(invd == 0.0f)
{
return (s > min && s < max);
}
float t0 = (min - s) * invd;
float t1 = (max - s) * invd;
if(t1 < t0)
{
float temp = t0;
t0 = t1;
t1 = temp;
}

if (t0 > t_exit || t1 < t_enter)
return false;

if(t0 > t_enter) t_enter = t0;
if(t1 < t_exit) t_exit = t1;
return true;
}


Vector dir(end - start);
Vector invDir((fabs(dir.x) < 0.00001f)? 0.0f : 1.0f / dir.x,
(fabs(dir.y) < 0.00001f)? 0.0f : 1.0f / dir.y);

bool intersectSegmentRectangle(const Vector& start, const Vector& end, const Vector& invDir, const Vector& min, const Vector& max, float &t)
{
float t_enter = 0.0f;
float t_exit = 1.0f;

if (!AxisIntersect(start.x, invDir.x, min.x, max.x, t_enter, t_exit)) return false;
if (!AxisIntersect(start.y, invDir.y, min.y, max.y, t_enter, t_exit)) return false;

t = t_enter;

return true;
}



Share this post


Link to post
Share on other sites
Nice oliii , really cool .

Could you please explain the arguments in more detail , I.e what is the s , e , min ,max ......

By the way you are welcome before breakfast , before lunch ,and also before dinner. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Emil_Halim
Could you please explain the arguments in more detail , I.e what is the s , e , min ,max ......
AxisIntersect() is a support function, so you don't really need to worry about it (apart from understanding how the algorithm works, that is). As for the intersection function:
bool intersectSegmentRectangle(const Vector& start, const Vector& end, const Vector& min, const Vector& max, float &t);

start : start point of line segment
end : end point of line segment
min : 'min' corner of AABB
max : 'max' corner of AABB
t : if an intersection is detected, the parametric value corresponding
to the first point of intersection will be written to this variable

The function returns 'true' if an intersection was detected, and 'false' otherwise.

Share this post


Link to post
Share on other sites

ok now I understand it well , thanks.

by the way , the min point of AABB means that minmum x and minmum y of the 2 points and also the same for maxmum x,y.

Share this post


Link to post
Share on other sites
I recommend creating a class to represent an intersection operation, this way relevant information can be stored in a sensible way and not passed around with in/out args or return values that aren't the entirety of what a function computes.

This also (imho) reminds the programmer that these operations are not cheap.

so, without further ado:



// a useful tool
template<typename T> void EnforceOrder(T & a, T & b){
if(a > b) swap(a,b);
}

struct line{
vec2 pt; // a point on the line
vec2 dir; // the direction of the line (this vector is parallel to the line)
};

struct AABB{
vec2 bl; // bottom left point
vec2 tr; // top right point
};

class IntersectLineAABB{
public:
bool isect; // true if there is an intersection

// the solutions (NOT coordinates) for the intersections
// these values are the offsets along the line of the intersections
float sol_low;
float sol_high;

// remember the line so we can access it
const line & L;

IntersectLineAABB(const line & LINE, const AABB & box):L(LINE){
isect = false;

// degenerate cases
// warning: we ASSUME that L.dir is not (0,0)
if(L.dir.x == 0.0){
if(L.pt.x < box.bl.x || L.pt.x > box.tr.x) return;
else{
isect = true;
sol_low= (box.bl.y - L.pt.y)/L.dir.y;
sol_high = (box.tr.y - L.pt.y)/L.dir.y;
EnforceOrder(sol_low, sol_high);
return;
}
}
if(L.dir.y == 0.0){
if(L.pt.y < box.bl.y || L.pt.y > box.tr.y) return;
else{
isect = true;
sol_low = (box.bl.x - L.pt.x)/L.dir.x;
sol_high = (box.tr.x - L.pt.x)/L.dir.x;
EnforceOrder(sol_low, sol_high);
return;
}
}

float xlow, xhigh; // solution values in x
float ylow, yhigh; // solution values in y

// no trivial exclusion, solve normally
xlow = (box.bl.x - L.pt.x)/L.dir.x;
xhigh = (box.tr.x - L.pt.x)/L.dir.x;

ylow = (box.bl.y - L.pt.y)/L.dir.y;
yhigh = (box.tr.y - L.pt.y)/L.dir.y;

EnforceOrder(xlow, xhigh);
EnforceOrder(ylow, yhigh);

// if the solutions overlap then an intersection exists
if(xlow > ylow && xlow < yhigh){
sol_low = xlow;
sol_high = min(xhigh, yhigh);
isect = true;
}else if(ylow > xlow && ylow < xhigh){
sol_low = ylow;
sol_high = min(xhigh, yhigh);
isect = true;
}
}

// returns true if there is an intersection
inline bool valid(){return isect;}

// returns the location of the low-valued intersection
inline vec2 lowpt(){return L.pt + (L.dir * sol_low);

// returns the location of the high-valued intersection
inline vec2 highpt(){return L.pt + (L.dir * sol_high);

// returns the solution vector
inline vec2 solution(){return vec2(sol_low, sol_high);
};



note that if you're intersecting with a segment (line connecting two points) or a ray (an infinite line in ONE direction from a point, this code is still good for you, just remember the solution values are constrained ([0,1] for a segment, and >=0 for a ray).

Also, for the code-conscious, this code is not verbatim what I have in my libs (though it is functionally equivalent), so don't bother commenting on style or whatever.

final note; to do NON axis aligned bounding boxes, I like the clipping planes solution, do that.

Share this post


Link to post
Share on other sites
BTW, what's cool with that ray-segment intersect method is that you can extend it easily to do much more interesting things. Namely, moving convex polygon-polygon collision (boxes, oriented boxes, triangles, convex polygons, ...).

a discussion about this.

http://www.gamedev.net/community/forums/topic.asp?topic_id=346956

And further extend it to get the points and normal of collisions. And then ultimately the points of contact.

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii

a discussion about this.

http://www.gamedev.net/community/forums/topic.asp?topic_id=346956



Oliii , your link is very helpful , and i think that topic must be sticky , it will help a lot for many ppl.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement