Narrow Phase Collision Detection Using Density Fields: Results
But it took a while. The biggest problem I encountered in implementing my scheme was due to slight inaccuracies in the construction of the surfaces from the polygonization algorithm that ended up causing noticeable detection problems when meshes were scaled up. To fix it, I implemented a pseudo-binary search to ensure that the algorithm places vertices at points at which the absolute value of the density function is no more than some very small error tolerance, ensuring that the algorithm stays as true to the real surface as possible. Linear interpolation of the density function just isn't good enough when you introduce metaballs with variable power (i.e., to create rectilinear shapes), which can cause sharp, sudden variations in the density function.
After increasing the precision of the polygonized surfaces, the detection worked like a charm! The time required to check two bodies is highly dependent on the resolution of the point set used for the first body. I found that it generally sufficed to use point sets generated from low-resolution meshes for the collision. With optimization, I can get the checking time down to around 0.1 ms per check.