- 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?
Sweep&prune implementation
Author
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
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 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
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
