Collision Detection Performance

[nithinp7]

By my understanding, Pies should be performance-bottlenecked on the Cholesky refactorization that happens every frame due to collision constraints added / removed from the system matrix - instead we are currently bottlenecked by the performance of collision detection itself. Possible avenues for collision detection performance improvement are described below.

The original acceleration structure we used for the collision system was a parallelized spatial hash, since this was ideal for the particle-contact search we had originally planned to do. We are finding that the performance of the spatial hash in swept-triangle contact culling is highly variable - particularly large, skinny, or fast triangles perform very poorly during spatial hash insertion as well as during spatial hash queries. In those cases, we often have to check many spatial hash grid cells to conservatively cover the swept shape over an interval. Unlike the particle collision case, it is also unclear how to pick a good spatial hash grid size that works for all triangles - as a result the current implementation imposes the burden of choosing reasonably consistent tessellations and choosing a corresponding spatial hash grid size on the user. Since these parameters are hard to tune by hand, I suspect the performance of the typical use case is suboptimal currently. It may be better to implement a BVH based acceleration structure instead, that is more typically seen as a broad-phase for triangle CCD in the literature.

Lastly, in implementing the triangle-triangle CCD, we used a generic root-finding algorithm built into Eigen. We suspect this is not as efficient for our use case, since we should early-exit in the case of imaginary roots or roots outside the t=[0,1] interval. We found the paper “High-Performance Polynomial Root Finding For Graphics”, Cem Yuksel et al., and prototyped a partial implementation of their approach, but did not have time to finish it. We suspect that along with the proper BVH broadphase mentioned above, the specialized Newton-method approach mentioned in the paper would significantly improve our collision detection performance.