Archived

This topic is now archived and is closed to further replies.

Hobitz

Sweep&prune implementation

Recommended Posts

Hi to all, right now am working on collision detection for my project and actually trying to implement sweep&prune for first stage collision filter. In teory its sounds realy easy but in practice its a bit harder that i expected. Problem is how to actually find which objects intersect? I have two methods in my mind: 1) Classical approach i think is to sort list of mins and maxs (for each axis) with bubble sort and if two nodes swap we look for intersection and flag it somewhere if its happen. This approach needs some storage where to put theese flags. So, i think its not the better way, because of that storage. 2)Second is to take an object and project it to each axis[list of mins and maxs] and look if its intersect with something. In that case i do not need any storage for marking intersection, but before i project my object i need to update and sort theese three lists so process can look like that: 1.Update mins and maxs (aabb from object rotation) 2.Sort my axis lists of mins and maxs 3.Go trought all objects and project them to that axis, what means O(n), i think!? Well, in my option the second one sounds beter but am thinking about how to merge update and sort so i can only project object on that axis, it can be optimized somehow? So if i totally wrong about all that corect me please. And is there any other dimension reduction algos that can be used for first pass collision filter, except sphere-trees?

Share this post


Link to post
Share on other sites
the sweep and prune would get my thumbs up for it''s simplicity and speed. Although, it requires loads of sorting, especially if you have a 2-axis sweep and prune.

for a one axis sweep and prune, it''s straight forward enough. find the projection (min, max) along the axis, insert-sort the span into the list, sorted by min values. Also, double book-keeping, or whatever it''s called (it''s just keeping a reference to the position of the object in the list), improves speed a lot, since objects aren''t likely to move a lot, so from frame to frame, all you have is move the object''s position in the list up or down.

when scanning the list, scan stop at each elements, and test elements further up the list until those elements stop intersecting the current element in check.

something like


for(i, [0, num[)
{
for(j, [i+1, num[)
{
if (span[i
].max >= span[j].min)
{
test intersection(span[i].collobject, span[j].collobject)
}
else
{
break;
}
}
}


for a 2-axis sweep and prune, it''s a bit more complicated. I don;t know if it''s the best way, but for each axis, I also have a list of pairs of objects which have their span intersecting for that axis.

I run the algo above, but instead of testing intersection, I store the pair of indices of objects in a sorted list. It''s not too costly, since all pairs involving object will be inserted close to the first insertion.

so, something like that


struct CSpan
{
float min;
float max;
u_short index;
};

list<CSpan> spans;
list<u_int> pairs;

for(i, [0, num[)
{
for(j, [i+1, num[)
{
if (spans[i
].max >= spans[j].min)
{
pairs.Insert((spans[i].index << 16) + spans[j].index)
}
else
{
break;
}
}
}


I do that on both axis, and end up with two lists, say pairsX and pairsZ.

then I scan the two lists to find elements present in both lists. these are the candidates for intersection. Since the list
are already sorted, the ''AND'' operation on the two lists is quick.

if I had 3 axes, say another on one the Y axis, instead of intersecting objects, I''d store the pairs present in the two lists pairsX and pairsZ into another list, pairsXZ, sort of a ''AND'' operator of the two lists pairsX and pairsZ. then it''s another ''AND'' operation between pairsY and pairsXZ.

you are limited to 65000 objects, but I doubt you''ll ever use that many. Else, move to 64 bits

Share this post


Link to post
Share on other sites