soulwire/Coffee-Physics — pull request #1 by kirbysayshi (2012-03-01 05:45:33+00:00)
Title: Hierarchical Spatial Hash Grid (HSHG) for collision detection speed

Hello!

I've been working on an implementation of a 3D spatial hashing algorithm specifically created for efficient broad-phase collision detection between variously-sized (even extremely so!) objects in infinite 3D space. I've been working on a simple physics engine to demo it, but when I saw Coffee-Physics on Twitter today, I figured it was perfect!

So I've done a few things, as my commit messages should explain. The two most affecting changes to existing code were:

* An additional behaviors array to the physics world, that instead of acting on each particle, acts on the world as a whole. This was necessary because the HSHG needs to look at all bodies at once, as well as be told when to update each entity's grid information.
* Particle got a new method, getAABB(), which is the one external interface requirement for the HSHG. I realize that it doesn't make a ton of sense for a particle to have an AABB, but it _does_ make sense when you consider than any body that has a getAABB method can be added to the grid for efficient broad phase detection... meaning you could create a system of springs and particles, give that construct a getAABB method, and detection will _just work_.

I've added two demos. Each shows a marked increase in framerate, due to the HSHG. For example, on my laptop using Chrome 17, the attraction demo tops out at 30fps, churns down to 20, and slowly counts down from there. My HSHG attraction demo gets a steady 60fps! It's even sort of useable in FF!

FYI This is my first time writing coffeescript.

I realize that this is a big injection, but I really couldn't resist after seeing the nice platform you've built here.

Thoughts?