Writing a Collision Detection Library. Need guidance.

[Orm]

Here is the thing, I am working on a 2D game for my semester project and am looking to make it in such a way that will allow me to expand the resulting framework easily into a 2D game engine, specifically for the broadphase collision detection. The algorithm I have been looking at implementing for this is the sweep and prune algorithm, although such an algorithm I have read is no better than brute force unless it is further optimized by a structure such as an octree. My question is this, are there any other broadphase algorithms that are possibly easier to implement than S&P and offer at least a slight performance gain over brute force? My plan is to use the results of this project to begin work on a full 3D game engine that will be my pet-project throughout my college years. I have searched on forums, google, and all across gamedev and have not found any other solution, and I figured that a community that revolves around the subject would be the best place to ask and learn from. My classes that will power the collision detection library are ready, all I need is to find a good and simple algorithm to power the collision detection until I have better knowledge and can implement a better algorithm. Normally I would be looking at either Box2D or Bullet, but the Professor wants us to go as low level as we can, so I am settling for OpenGL and whatever else I can cook up. I am no stranger to basic sphere-sphere and AABB-AABB collisions, and I would also like to say that I understand raycasting as well. I would like to know the best ways there are to optimize these checks. So can someone please offer me guidance on the subject or at least a kick in the rear pointing me in the right direction?

Also, any advice that any experienced developers can give me I would also greatly appreciate.

Thank you,
-Mike

[fishboy82]

I am not an expert on collision detection too ，but I could give you some opinion which I hope will help you.
The BroadPhase Method I know is SAP and Space Hash,The wildly used is SAP and space Hashing is very popular used in deformable body collision detection. So I recommand to use SAP for it's popularity>.<
The NarrowPhase I recommand use SAT Method for it's implicity ,of course if you are an expert you may prefer use GJK as Bullet do which is more general, Also you can use specialized method for specilized primitive e.g box vs sphere which may be accelerate the speed,etc.
Basically I think to allow user to config their own collision detection algo is very important like Bullet do.
Hope's these may help you a little

[Orm]

Yes, your recommendations did help me out a bit. I'll look into space hashing, but am still open to any other suggestions.

[dneckels]

Not an expert at collision, either, but I do have a working 3D implementation.

I would question the advice you were given on the Sweep and Prune. It reduces an N^2 check of bounding boxes to an N log(N) one, and, using temporal coherence, to an N complexity search. Very fast.

I've seen octrees do amazing things. Perhaps your sweep and prune could be augmented by a higher level (larger space) octree.

Also a big fan of RCB (Recursive coordinate Bisection), though I don't see many references to it in the graphics literature.... Very simple to implement using halfspaces.

cheers

[aokman]

My question is this, are there any other broadphase algorithms that are possibly easier to implement than S&P and offer at least a slight performance gain over brute force?

Maybe you can try BVH(Bounding Volume Hierarchy), which is initially used for accelerating ray tracing algorithm. BVH can not only be used as broadphase algorithm, but also can be used as a whole set of collision detection and response in its own right(just as a alterative to Otree when used in ray shooting problem. Many FPS game use ray shooting to do collision detection and response, instead of a whole physics engine).

The main idea of BVH can be found in many papers and books. For example, 'Real-Time Collision Detection' is a good one to describe this. And papers are:
Automatic Creation of Object Hierarchies for Ray Tracing of Dynamic Scenes
Automatic Creation of Object Hierarchies for Ray Tracing

Bullet also uses two BVH(called DBVH for double BVH) for its Broadphase collsion detection, one for static objects, and the other for dynamic objects. In the comments of Bullet's source code, it is declared that DBVH is more efficient than Swap-and-prune in large scale scenes with a log complexity.

[Orm]

Hmm, I'll look into both of those. For now I'm using the brute force algorithm that avoids double checking the volumes, so I'll look at trying to implement those when I get more time. This whole thing has given me an idea of just how bad, nay awful some of my design ideas have been. For example., to associate a bounding volume with a game entity, I'm having to use a combination of numerical and char* ID's (where the entity ID and BoundingVolume ID match) and a quicksearch algorithm to avoid having dangling pointers in the Collision Solvers internal list, as would occur if I were to call delete on the bounding volume on the destruction of the game entity. It works well if I wanted to integrate it directly with the rest of my framework, but my design goals were to modularize the code as much as possible. If someone wants to look at the relevant class declarations and offer some advice, I'll be happy to paste them here.