Well I went with a simple sorting of axis-aligned bounding box coordinates, having each corner belong to 3 special linked lists, one for each axis. I use a simple sort because it is fairly quick when you have reasonable frame-to-frame coherency, meaning it doesn't take a lot of CPU effort to keep things sorted because spatial relations don't change drastically from frame to frame.

Pseudo-code:



Link together and maintain sort of all LowerCorner.x and UpperCorner.x,
Link together and maintain sort of all LowerCorner.y and UpperCorner.y,
Link together and maintain sort of all LowerCorner.z and UpperCorner.z,

While sorting, keep track of sort order along each axis so that you know how many corner elements between the lower corner and upper corner components. Choose the one with the least number, and then check for collision only with those corner elements between the lower corner and upper corner along the chosen axis.

I had tolerable performance even with 1500 rapidly moving entities.

Value of good ideas: 10 cents per dozen.
Implementation of the good ideas: Priceless.
Proxima Rebellion - A 3D action sim with a hint of strategy

[edited by - BS-er on March 27, 2003 11:31:55 PM]