Jump to content
  • Advertisement
Sign in to follow this  
Emil_Halim

Fastest code of 2D line intersected with rectangle

This topic is 3965 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!