# Narrow Phase Collision Detection Using Density Fields

June 17, 2011

I've been pondering narrow phase collision detection a lot lately, as it's really the only thing that stands between me and a working space shooter demo. Unfortunately, it's not at all an easy problem, especially considering the fact that I have on-the-fly meshes generated and can make no assumptions about the topology, nor can I rely on hand-construction of bounding trees.

I had been getting pretty excited about an idea I had that involved a two-phase check using AABB-trees for pruning and then spatial bucketing (a la spatial hashing) for triangle-to-triangle testing. Then it hit me: why am I running in circles? I started with a mathematical model of the mesh: an isosurface of a well-defined density function. I used a complex algorithm to convert the isosurface into a polygonized mesh. Now I was trying to go back to a mathematical representation that would be conducive to collision detection. Why??

Here's the punchline: why not use the original density field description for checking? After all...the density field is even more precise than the triangular mesh! All that collision detection really is, thanks to the nature of my engine, is a solver for the intersection of two isosurfaces, both of which can be completely described using formulae! Of course, I'm sure the math would get incredibly nasty for an analytic solution, and I'm not really up for exploring that option at the moment. But here's a better idea: use a set of points (the vertex positions generated by the polygonization algorithm) to describe one isosurface, then check each point against the other surface's density function. Then, if you ever find a sign change, you immediately know that there's a collision!

This is a pretty cool idea, since it only requires a set of points and a density function to work. It definitely avoids a lot of mess associated with computing BVHs. Most importantly, however, it just makes sense! If you're working with a precise, mathematical definition of a surface, then use it!

I'll probably be implementing a rough draft of this system quite soon, so we'll see if it measures up to my expectations. I would imagine that sampling the density function will be cheaper than other types of collision detection, but I'll need to do some extensive profiling to make sure that this idea is actually as clever as I believe it to be.