A hierarchic collision detection algorithm for simple Brownian dynamics

We describe an algorithm to avoid steric violation (bumps) between bodies arranged in a hierarchy. The algorithm recursively directs the focus of a bump-detector towards the interactions of children whose parents are in collision. This has the effect of concentrating available computer resources towards maintaining good steric interactions in the region where bodies are colliding. The algorithm was implemented and tested under two programming environments: a graphical environment, OpenGL under Java3D, and a non-graphical environment in “C”. The former used a built-in collision detection system whereas the latter used a simple algorithm devised previously for the interaction of “soft” bodies. This simpler system was found to run much faster (by 50-fold) even after allowing for time spent on graphical activity and was also better at preventing steric violations. With a hierarchy of three levels of 100, the non-graphical implementation was able to simulate a million atomic bodies for 100,000 steps in 12 h on a laptop computer.