Jump to content
  • Advertisement
Sign in to follow this  

Sweep Line Algorithm

This topic is 2445 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

I'm currently reading David Eberly's Game Physics, and I have a question concerning the sweep line algorithm presented at the end of the 5th chapter. The algorithm and its presentation seem straightforward enough, but I'm wondering why there's a need to maintain sorted lists of x and y intervals. If the condition for the intersection of two 2D rectangles is that both the x and y extents must overlap, then why isn't it sufficient to maintain a sorted list for one dimension, and then if an intersection is detected in one dimension, perform a check for intersection in the other dimension on the rectangles themselves.

I'd greatly appreciate any and all insights. Thanks.

Share this post


Link to post
Share on other sites
Advertisement
What you suggest works for the initial sort of the boxes. However, when you start moving the boxes and updating each frame, a sort only on x is not sufficient. Consider box0 with 0 <= x <= 2 and 0 <= y <= 2. Consider box1 with 1 <= x <= 3 and 1 <= y <= 3. In the initial sort on x, you find that x-intervals [0,2] and [1,3] overlap, so then you test for box-box overlap and find the boxes intersect. Suppose box1 is moved to 1 <= x <= 3 and 3 <= y <= 4; that is, the box is moved in the y-direction. The two boxes are no longer overlapping, so you need to remove the pair from the overlap set. If you only sort on x, you would never enter the insertion-sort swap code because the x-endpoints have not changed at all (the x-list is still correctly ordered).

Share this post


Link to post
Share on other sites
Dr. Eberly,

First let me say thank you for your reply and for your contributions. I've quite enjoyed reading your books for some time now.

I had thought that a loop like that which initializes the algorithm, and which inserts intersecting rectangle indices in the overlap set (using an AABB instance method to check y overlap) could also be used to remove such intervals from the overlap set when they only intersected in x but not on y. I've stared a little harder at your example code (in WmlIntersectingRectangles.cpp), and it's clearer to me now that maintaining two lists is necessary to efficiently leverage spatial and temporal cohesion.

Now, I can write some sketches and try this out on my own. Thank you!

What you suggest works for the initial sort of the boxes. However, when you start moving the boxes and updating each frame, a sort only on x is not sufficient. Consider box0 with 0 <= x <= 2 and 0 <= y <= 2. Consider box1 with 1 <= x <= 3 and 1 <= y <= 3. In the initial sort on x, you find that x-intervals [0,2] and [1,3] overlap, so then you test for box-box overlap and find the boxes intersect. Suppose box1 is moved to 1 <= x <= 3 and 3 <= y <= 4; that is, the box is moved in the y-direction. The two boxes are no longer overlapping, so you need to remove the pair from the overlap set. If you only sort on x, you would never enter the insertion-sort swap code because the x-endpoints have not changed at all (the x-list is still correctly ordered).

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!