Sweep&prune implementation

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

Thanx! It was help a lot!