Multigrid contact detection method

Contact detection is a general problem of many physical simulations. This work presents a $O\left(N\right)$ multigrid method for general contact detection problems (MGCD). The multigrid idea is integrated with contact detection problems. Both the time complexity and memory consumption of the MGCD are $O\left(N\right)$. Unlike other methods, whose efficiencies are influenced strongly by the object size distribution, the performance of MGCD is insensitive to the object size distribution. We compare the MGCD with the no binary search (NBS) method and the multilevel boxing method in three dimensions for both time complexity and memory consumption. For objects with similar size, the MGCD is as good as the NBS method, both of which outperform the multilevel boxing method regarding memory consumption. For objects with diverse size, the MGCD outperform both the NBS method and the multilevel boxing method. We use the MGCD to solve the contact detection problem for a granular simulation system based on the discrete element method. From this granular simulation, we get the density property of monosize packing and binary packing with size ratio equal to 10. The packing density for monosize particles is 0.636. For binary packing with size ratio equal to 10, when the number of small particles is 300 times as the number of big particles, the maximal packing density 0.824 is achieved.

Figure 1

Schematic view of a system with two grids in 2D. Objects are circles. (a) According to the objects’ size, they belong to different grid layers. (b) Objects in the system. (c) Layer 1: $S_{\text{native}}^1$ is shaded; $S_{\text{target}}^1-S_{\text{native}}^1$ is in white. (d) Layer 2: $S_{\text{native}}^2$ is shaded.

Figure 2

The contacts among small objects are detected in the fine grid. The contacts among big objects are detected in the coarse grid. The contacts between big objects and small objects are also detected in the coarse grid.

Figure 3

Performance comparison between MGCD (+,×), the multilevel boxing method (◻,◇), and NBS method (◁, ▷) for different object composition. The computing time is normalized by the number of objects. $\frac{W_b}{W_s}$ is 10. The number of big objects is ${10}^4$. Density is the sum of ${\rho }_b$ and ${\rho }_s$ $({\rho }_b+{\rho }_s)$. The host machine has one Pentium $42.8\mathrm{G}$ processor and $1\mathrm{GB}$ RAM. Due to excessive memory consuming, when the density is 0.1 and number of small objects is ${10}^7$, the data for the multilevel boxing method are not available.

Figure 4

The relationship between different size ratios and computing time. The computing time is normalized by the number of objects. $N_b$ is ${10}^4$, $W_b$ is $10\mathrm{cm}$, and the density $\left(\rho \right)$ is 0.1. $W_s$ varies from $1\text{to}10\mathrm{cm}$, $N_s$ (labeled in the figure) varies from ${10}^4$ to ${10}^7$, but $N_s\times W_s^3$ is kept fixed. The host machine is the same as the one for Fig. 3.

Figure 5

(a) Snapshot showing the formation of a binary packing of 200 big particles $(R_b=6.5\mathrm{mm})$ and 300 small particles $(R_s=3.9\mathrm{mm})$. (b) Schematic view of calculation cuboid in 2D. Here, $(\text{particles}\cap \text{calculation}\text{cuboid})$ is the shaded area, and the area of calculation cuboid is $L\times h$ [Eq. (17)].

Figure 6

The relationship between particle composition and packing density. The size ratio $\frac{R_b}{R_s}$ is 10. The number of big particles $N_b$ is fixed at 2000.

Figure 7

Uniform distribution.