Fastest code of 2D line intersected with rectangle
Author
Hi All
i am looking for the Fastest code of 2D line intersected with rectangle , and specify the intersected point.
any help please?
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.
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).
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).
Author
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.
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.
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
Author
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 ?
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 ?
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.
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
Author
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 ?
a quickie, jyk's method (and my choice too).
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 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;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
