Simulations require the detection of collisions and adjacencies between objects in order to compute forces and prevent interpenetration. Deforming molecules present an interesting challenge to extant collision systems, as current methods deal well only with rigid objects. Thus one is forced to either treat each atom independently, which is very expensive and does not exploit the coherence of the motion, or to treat entire molecules with bounding volume hierarchies meant for rigid objects, which means that these hierarchies have to be recomputed every few time steps.

Molecules, however, have useful structure that remains constant through deformation. For example, proteins remain connected along their backbone during most activities of interest. We have implemented hierarchical collision detection systems which take advantage of this coherence by structuring the hierarchy as a tree along the sequence defined by a linear object. The key insight of our methods is to focus on combinatorial descriptions of bounding volumes which stay constant for long periods, even though the actual volumes themselves change constantly. We developed two bounding box hierarchies optimized for different types of motions. The first focuses on individual atoms/spheres and uses minimum enclosing spheres to build the hierarchy. We exploit the fact that each such enclosing sphere is determined by at most four atom spheres to prove sub-quadratic worst-case bounds for collision detection. We also verified that the hierarchy is stable in a number of molecular dynamics simulations. The second considers motions controlled by torsion angles along the backbone. A software module implementing this approach shows that it neatly outperforms other state-of-the-art collision detection algorithms, when a conformation is incrementally modified, with few torsional angles changed at each increment (a situation common in many Monte Carlo simulators).