Hierarchical Spatial Hash Grid (HSHG) for collision detection speed

[kirbysayshi]

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?

[kirbysayshi]

I posted my changes so they're easily visible for inspection: http://kirbysayshi.github.com/Coffee-Physics

If you think this is ridiculous or against what you're going for, just let me know and I'll take it down.

[soulwire]

Hey Andrew,

This is great, thanks so much for writing and sharing it. What I'd like to do is work out first why the collision response is acting slightly differently and then this weekend I was planning on refactoring the collision anyway (similar to your idea, into the core engine but then allow the user to toggle collision on in the particle as a flag instead of a behaviour). So this way we could call some collision detection / response from the engine and then provide different methods, namely your HSHG implementation or an optimised version of the basic one.

So since I need to refactor anyway, I'll integrate your code manually if you're ok with that?

[kirbysayshi]

Sure, I think that's fine, whatever helps the most and is easiest for you!

As to why the collision response is acting slightly differently, I have two theories that have no actual evidence, just gut feelings:

• Because the worldBehaviours happens after particle position update, the collision response might be more likely to place the Particles into invalid (overlapping) positions
• The HSHG is missing collisions, and only detecting them later in their penetration. This is possible, as I'm unsure of how to write good tests for this thing. Suggestions are welcome!

In general, I notice that things seem "jumpy" (more so with the grid, but with the brute force collisions as well). I've seen this in my own experiments with position based dynamics, and this article seems to address this: http://codeflow.org/entries/2010/nov/29/verlet-collision-with-impulse-preservation/. I was in the middle of making something more versatile based on the article when you released Coffee-Physics :)

I've made a repo for HSHG: https://github.com/kirbysayshi/HSHG, so the preliminary tests I made are accessible.

[ericmick]

I think this is an awesome addition to an awesome project. I've been working on my own coffeescript physics engine off and on for a few months now and in my opinion this is exactly what is needed to scale up. I really excited to try this out and perhaps contribute.

[soulwire]

Thanks for the work @kirbysayshi - I've been able to revisit this project recently and implemented a quadtree which I'll merge to master soon. I appreciate the contribution and mentioned you in the commit as the inspiration for the change. I wanted to roll a CS version to provide with the project, you can check it out in the new branch.

[kirbysayshi]

Cool, glad to hear you're still working on this!