I’ve been rewriting the collision detection system for the last few weeks.  I have looked at several different collision detection algorithms over the years but the one that I keep coming back to is in a paper by Kasper Fauerby at peroxide.dk called “Improved Collision detection and Response.”  The primary reason I kept going back to that one is that it included information on the response step, not just how to detect collisions.  Unfortunately, it’s a little tough to follow in places and his code listings are in C++, so taking those and converting them to Javascript has been tricky.  After several attempts with varying degrees of success, I think I finally have it working.  I have a test scene with a sphere that just moves around the x-z plane.  I placed a few primitives (boxes and spheres) and a more complicated object modeled in Blender into the scene.  Without gravity it appears to be working perfectly right now.  The algorithm handles multiple objects close together and non-convex objects as well.  I only have a few objects in the scene but I don’t see a significant impact on performance so far.

This is very, very exciting as is but there are several things I need to implement or improve:

• Code refactoring
  • Up to this point I’ve been trying to transcribe the paper’s C++ straight into Javascript just to keep things simple.  There are some C++ conventions that just don’t make sense in Javascript (like reference variables) so I would like to rewrite the whole thing.
• Gravity
  • The Fauerby paper actually includes some information on how to implement this, so hopefully it will be easy.
• Broad phase collision detection
  • The current implementation runs the rather expensive collision detection algorithm on every object in the scene on every frame.  This is fine for a very limited number of objects but I need to implement a broad phase that can quickly eliminate objects that are far away and thus cannot collide with the player.  THREE automatically generates an axis aligned bounding box (AABB) for every object in a scene, so checking against those is likely the way to go.
• Spatial partitioning
  • In addition to a broad phase, I would like to use something like an octree to further optimize the collision detection system.  There are lots of good articles on this concept, but I probably won’t implement this immediately.

There are other things to do but these are the big ones.  I’ll probably spend the next several days rewriting the code, then stick in a broad phase check, then put the code into the game.  After that I’ll work on gravity, and save octrees for another day.

Overall I’m very excited because a reliable collision detection and response system will allow me to make a basic world that feels interactive.  I can then build off that by adding more “game” type features.