The contact detection methods aim at detecting potential physical contacts among all the objects in the system. Contact detection methods have numerous applications in various areas such as physically based simulations, granular materials, computer graphics, molecular dynamics (MD), and the discrete element method (DEM). Contact detection is usually the most computing-intensive process in the simulation of multiple discrete objects.

MGCD (Multigrid Contact Detection)

MGCD (Multigrid Contact Detection) method integrated the idea of multigrid with contact detection problems. MGCD solves different ranges of contacts at grids with different coarsenesses.

It is a O(N) multigrid method for general contact detection problems. Both the time complexity and memory consumption of the MGCD are O(N). Unlike many other methods, whose efficiencies are influenced strongly by the object size distribution, the performance of MGCD is insensitive to the object size distribution. It is very efficient and suitable for solving the contact detection problem of large-scale system composed of polydisperse objects (objects with different sizes). For more information, please see the Reference page.

libmgcd

Libmgcd is an open source C implementation of the Multi Grid Contact Detection method. It can be applied to general contact detection problems as long as the objects in the physical system can be contained by Axis-aligned Bounding Boxes (AABBs). A list of AABBs is fed to the libmgcd library, and libmgcd returns a list of intersecting bodies.

Libmgcd has been tested in systems with up to ~10^7 objects.