I-COLLIDE library
Author
Hello,
I am reading a collision detection paper (ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/collision.pdf) about the algorithm of I-COLLIDE. There is
one paragraph as following:
"The one-dimensional sweep and prune algorithm begins by projecting each three-dimensional bounding box onto the x, y, and z axes. Because the bounding boxes are axis-aligned,
projecting them onto the coordinate axes results in intervals. We are interested in overlaps among these intervals, because a pair of bounding boxes can overlap if and only if their intervals overlap in all three dimensions. We construct three lists, one for each dimension. Each list contains the values of the endpoints of the intervals corresponding to that dimension. By sorting these lists, we can determine which intervals overlap. In the general case, such a sort would take O(nlogn)time, where n is the number of objects. We can reduce this time bound by keeping the sorted lists from the previous frame, changing only the values of the interval endpoints. In environments where the objects make relatively small movements between frames, the lists will be already nearly sorted, so we can sort in expected O(n) time. Bubble sort and insertion sort work well for previously sorted lists."
It seems a very good method. But I can not understand how to determine which intervals overlap only by sorting the endpoint of every interval. Of course, an interval is determined by a beginning point and an end point. Without the beginning point, how to determine if two intervals overlap only by their end point? Anyone can give me a guide? Thank you very much in advance.
Kidd
I spent a long time looking at the paragraph, and I was pretty confused as well. I spent a long time drawing out intervals and end points.
I think the confusion arises from the the words:
"Each list contains the values of the endpoints of the intervals ..." Endpoints here is plural and could refer to either the begin and end points of each of the intervals or could refer to only the endpoints of the intervals. Confusing huh? However, I think the paper is actually referring to both the begin and end points of each interval when they say "end points." Thus, for each bounding box, you are storing 6 values -- begin and endpoints for each of the three dimensions. Xmin, Xmax, Ymin, Ymax, Zmin, Zmax. The pair (Xmin, Xmax) is in the first list, (Ymax, Ymin) in the next, etc.
By storing both the begin and end points, you double the amount of memory you need, but the time analysis remains the same. Simply sort the values based on their minimums, then look for overlaps via a simple if statement.
Alexander "DmGoober" Jhin
alexjh@online.microsoft.com [Warning! This email account is not attended. All comments are the opinions of an individual employee and are not representative of Microsoft Corporation.]
[edited by - DmGoober on November 19, 2002 2:33:33 AM]
I think the confusion arises from the the words:
"Each list contains the values of the endpoints of the intervals ..." Endpoints here is plural and could refer to either the begin and end points of each of the intervals or could refer to only the endpoints of the intervals. Confusing huh? However, I think the paper is actually referring to both the begin and end points of each interval when they say "end points." Thus, for each bounding box, you are storing 6 values -- begin and endpoints for each of the three dimensions. Xmin, Xmax, Ymin, Ymax, Zmin, Zmax. The pair (Xmin, Xmax) is in the first list, (Ymax, Ymin) in the next, etc.
By storing both the begin and end points, you double the amount of memory you need, but the time analysis remains the same. Simply sort the values based on their minimums, then look for overlaps via a simple if statement.
Alexander "DmGoober" Jhin
alexjh@online.microsoft.com [Warning! This email account is not attended. All comments are the opinions of an individual employee and are not representative of Microsoft Corporation.]
[edited by - DmGoober on November 19, 2002 2:33:33 AM]
I impemented sweep and prune in our collision system. It''s main benefit is its speed if you can take advantage of coherrence.
What this means is you set up your sorted lists and then each game tick you use the previously sorted lists as a starting point for the next lists. If only one or a few objects have moved you can do a bubble sort to quickly update the sorted lists rather than having to use a more powerful technique.
Then as you sort you check each time two enpoints are swapped in case the swap cause the two objects in question to overlap. Again if a few or only one object is moving you will typically be doine only a few if any of these checks. You can also monitor swaps that un-overlap objects as a way of removing that pair of object from the list of those you are checking for impact.
And you don''t need to do all three axes. Our engine does only two as gravity and the shape of the world constrains most things to lie/sit on the ground. There''s no need to check the ''up'' axis as two objects overlapping on the other two axes are almost always overlapping on this one.
What this means is you set up your sorted lists and then each game tick you use the previously sorted lists as a starting point for the next lists. If only one or a few objects have moved you can do a bubble sort to quickly update the sorted lists rather than having to use a more powerful technique.
Then as you sort you check each time two enpoints are swapped in case the swap cause the two objects in question to overlap. Again if a few or only one object is moving you will typically be doine only a few if any of these checks. You can also monitor swaps that un-overlap objects as a way of removing that pair of object from the list of those you are checking for impact.
And you don''t need to do all three axes. Our engine does only two as gravity and the shape of the world constrains most things to lie/sit on the ground. There''s no need to check the ''up'' axis as two objects overlapping on the other two axes are almost always overlapping on this one.
Author
DmGoober, thanks for your reply. In fact, I had thought what you wrote. But if sorting both Xmin and Xmax in the same list, isn''t it a mess? Do you think if I sort only Xmin (or Xmax), but use an interval value to determine if two intervals overlap is more easier? The behind show the realization of this method.
1*----------
2*----------------
3*--------
4*--------
5*-----------
1. The list is sorted by Xmin
2. If the Xmin(1) + Interval(1) > Xmin(2), that means interval(1)
and interval(2) overlap. So need to check interval(1) and interval(3). They overlap too.
3. Xmin(1) + Inteval(1) < Xmin(4), that means no overlap between interval(1) and interval(4). So no need to check if overlap occurs between interval(1) and any other interval.
4. Begin to check the overlap between interval(2) and other intervals.
I do think this method is better than to sort both Xmin and Xmax. Can you show me how to get the overlaps with both Xmin and Xmax sorting easily? Thank you very much
Kidd
1*----------
2*----------------
3*--------
4*--------
5*-----------
1. The list is sorted by Xmin
2. If the Xmin(1) + Interval(1) > Xmin(2), that means interval(1)
and interval(2) overlap. So need to check interval(1) and interval(3). They overlap too.
3. Xmin(1) + Inteval(1) < Xmin(4), that means no overlap between interval(1) and interval(4). So no need to check if overlap occurs between interval(1) and any other interval.
4. Begin to check the overlap between interval(2) and other intervals.
I do think this method is better than to sort both Xmin and Xmax. Can you show me how to get the overlaps with both Xmin and Xmax sorting easily? Thank you very much
Kidd
Author
oh. sorry. The picture in the previous message should be as following. It just ate all the backspace. * means the Xmin and ------- means interval. thanks
1*----------------
2222222*-----------------
3333333333333*---------
44444444444444444444*------------
555555555555555555555555*----------
1*----------------
2222222*-----------------
3333333333333*---------
44444444444444444444*------------
555555555555555555555555*----------
Author
hello johnb, thank you for your reply. I can not understand "Then as you sort you check each time two endpoints are swapped in case the swap cause the two objects in question to overlap" in your message. Sorry for this, I am not from an English country. Still the same question in my previous message. Did you sort both the begin point and endpoint of the same axes in the same list? If so, how to find all the overlaps easily? do you think the method I mentioned in the previous message is fast to get all the overlaps. Thanks
Kidd
Kidd
hello johnb, thank you for your reply. I can not understand "Then as you sort you check each time two endpoints are swapped in case the swap cause the two objects in question to overlap" in your message. Sorry for this, I am not from an English country. Still the same question in my previous message.
> Did you sort both the begin point and endpoint of the same
> axes in the same list?
Yes. They are calculated as pos.x/y/z +/- radius, where the raius is that of the bounding sphere.
> If so, how to find all the overlaps easily?
Every game step, i.e. each time the objects move, you re-sort the lists. Generally a bubble sort will do. As you do so add a check into each swap of the sort. The check is:
"if points A and B need to be swapped because A is now greater than B, and A is the upper bound of an object while B is the lower bound of an object, then this pair of objects is now overlapping on this axis"
This sounds complex but it''s easy to code as long as you can identify upper and lower bounds.
You then check their overlap on the other axis/axes, and if they overlap then add them to list of overlapping objects which you do further tests on.
There''s a similar check to remove objects from the list as they stop overlapping, e.g.
"if points A and B need to be swapped because A is now greater than B, and A is the LOWER bound of an object while B is the UPPER bound of an object, then this pair of objects is no longer overlapping on this axis"
> do you think the method I mentioned in the previous message
> is fast to get all the overlaps.
Sweep and prune is pretty fast. It has the advantage of working in linear or better time, i.e. if you double the number of objects your checks take only twice as long. If only a few objects are moving it can be especially fast, as then the resorting is quick and detects few new pairs each game step.
> Did you sort both the begin point and endpoint of the same
> axes in the same list?
Yes. They are calculated as pos.x/y/z +/- radius, where the raius is that of the bounding sphere.
> If so, how to find all the overlaps easily?
Every game step, i.e. each time the objects move, you re-sort the lists. Generally a bubble sort will do. As you do so add a check into each swap of the sort. The check is:
"if points A and B need to be swapped because A is now greater than B, and A is the upper bound of an object while B is the lower bound of an object, then this pair of objects is now overlapping on this axis"
This sounds complex but it''s easy to code as long as you can identify upper and lower bounds.
You then check their overlap on the other axis/axes, and if they overlap then add them to list of overlapping objects which you do further tests on.
There''s a similar check to remove objects from the list as they stop overlapping, e.g.
"if points A and B need to be swapped because A is now greater than B, and A is the LOWER bound of an object while B is the UPPER bound of an object, then this pair of objects is no longer overlapping on this axis"
> do you think the method I mentioned in the previous message
> is fast to get all the overlaps.
Sweep and prune is pretty fast. It has the advantage of working in linear or better time, i.e. if you double the number of objects your checks take only twice as long. If only a few objects are moving it can be especially fast, as then the resorting is quick and detects few new pairs each game step.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement