I re-sort the whole array on a single every frame using a radix sort. After that I sweep the array for overlapping intervals, just as its done in any sort and sweep implementation.
My question is, are there any special optimizations I can make for the "Sweep" part of the algorithm? I did some profiling on a scene with 20,000 objects stacked in a pyramid shape and I have found that the sort part of my implementation runs about 550 times per second, while the sweep part only runs about 30 times per second.
There is clearly some room for improvement on the sweep part but I cant think of any way to make it faster. I have looked at bullets SAP and I cant quite figure out what is going on. Are all 3 axis being sorted? If so how are you able to keep track of all the pairs? In my case, and array to keep track of overlapping axis of size 20,000 by 20,000 is not really an option.
Also, is there any way to optimize for "sleeping" objects? Im finding that even when objects fall asleep, the sort and sweep still must perform the whole task for all objects.
Just for the record, here is the sweep part of what I have written:
Code: Select all
for (int i=0;i<numBodies;i++)
{
for (int j=i+1;j<numBodies;j++)
{
if (outarray[j].x - outarray[i].x > outarray[i].radius * 2.0f)
break;
else if ( abs(outarray[j].y - outarray[i].y) < outarray[i].radius + outarray[j].radius)
pairs.add(outarray[i].ID, outarray[j].ID);
}
}