Multi-sphere shape generator for DEM simulations of complex-shaped particles

This paper introduces MSS, a novel algorithm that generates multi-sphere representations of complex-shaped particles for DEM simulations, offering superior shape approximation accuracy at lower computational costs compared to existing methods.

The Gist

Imagine you are trying to build a perfect replica of a complex object—like a human femur bone or a jagged grain of sand—using only a pile of smooth, round marbles. This is exactly the challenge scientists face when they want to simulate how sand, soil, or powders behave in computer models.

In the world of engineering and physics, this is called DEM (Discrete Element Method). To make the computer understand a weirdly shaped rock, scientists break it down into a cluster of overlapping spheres (marbles). The better the cluster fits the original shape, the more accurate the simulation.

However, finding the perfect arrangement of marbles is like trying to fill a complex-shaped cookie jar with marbles without leaving gaps or poking out too far. Previous methods were often slow, required a lot of manual tweaking, or ended up with "bumpy" marbles that made the simulation look unrealistic.

This paper introduces a new, smarter tool called MSS (Multi-Sphere Shape). Here is how it works, explained through simple analogies:

1. The "Heat Map" Strategy (Euclidean Distance Transform)

Imagine you have a 3D map of your target object (say, a bone). Instead of looking at the surface, MSS looks at the "depth" of the object.

• The Analogy: Think of the object as a mountain range. MSS creates a "heat map" where the center of the mountain is the hottest (deepest) point, and the temperature drops as you get closer to the edge.
• The Move: MSS finds the hottest spots (the deepest parts of the object) and places a marble there. The size of the marble is determined by how "hot" that spot is—meaning, how much space is available around it before hitting the edge.

2. The "Refinement" Game (Iterative Improvement)

Once the first big marbles are placed, there are still gaps or awkward corners left over.

• The Analogy: Imagine you are filling a puzzle. You put in the big pieces first. Now, you look at the remaining empty spaces. MSS calculates exactly where the next piece should go to fill the biggest remaining hole.
• The Magic: It doesn't just guess. It uses a mathematical trick (subtracting the current shape from the target shape) to find the "best fit" spot for the next marble. It repeats this process, adding marbles one by one, until the shape is perfect.

3. Why MSS is a Game-Changer

The authors compared their new tool (MSS) against the current "champion" tool (called Clump). Here is why MSS wins:

• It's Faster: MSS is like a sprinter compared to a marathon runner. It builds the same accurate shape in a fraction of the time.
• It Needs No "Tuning": The old tools were like a complicated radio; you had to twist three or four knobs (parameters) to get the sound right, and if you guessed wrong, the result was bad. MSS is like a modern smartphone: you just press "Go," and it figures out the best settings automatically.
• It Keeps the Shape Smooth: The old tools sometimes added tiny, unnecessary marbles that made the surface look bumpy and fake (like a potato covered in pimples). MSS avoids this, keeping the surface smooth and true to the original object's symmetry.
• It Handles "Breaking" Objects: In real life, rocks break and change shape. Because MSS is so fast and accurate, it can update the marble-cluster model while the simulation is running, allowing scientists to simulate rocks shattering or deforming in real-time.

The Bottom Line

This paper presents a new, automatic, and super-fast way to turn any complex 3D shape into a cluster of spheres for computer simulations.

Think of it this way: If the old method was like trying to build a castle out of sand using a spoon and a lot of trial-and-error, MSS is like having a 3D printer that instantly knows exactly how to pack the sand grains to match the blueprint perfectly, every single time, without you having to touch a single dial.

This allows scientists to simulate everything from landslides to industrial powder mixing with much higher accuracy and much less computing power.

Technical Summary

Here is a detailed technical summary of the paper "Multi-sphere shape generator for DEM simulations of complex-shaped particles" by Buchele, Pöschel, and Müller.

1. Problem Statement

In Discrete Element Method (DEM) simulations, the mechanical and rheological properties of granular materials are heavily dependent on particle shape. While the multi-sphere approach (representing complex particles as a cluster of overlapping spheres) is the standard method for simulating non-spherical particles, it faces significant challenges:

• Accuracy vs. Efficiency Trade-off: Representing complex shapes (especially those with sharp edges or smooth curves) requires a large number of spheres. Since computational cost in DEM scales with the number of spheres, using too many spheres makes simulations prohibitively expensive.
• Optimization Difficulty: Existing algorithms struggle to determine the optimal radii and positions of spheres to minimize the volume difference between the target shape and the sphere cluster without introducing artificial surface roughness or losing symmetry.
• Parameter Sensitivity: Many existing generators require extensive user-defined parameters that must be tuned empirically for each specific particle shape, making them difficult to automate.

The goal is to develop an algorithm that generates a multi-sphere representation of an arbitrary 3D shape with maximum accuracy using the minimum number of spheres, while maintaining low computational cost and avoiding the need for manual parameter tuning.

2. Methodology: The MSS Algorithm

The authors propose MSS (Multi-Sphere Shape), an iterative algorithm based on the Euclidean Distance Transform (EDT). The process is outlined as follows:

A. Input Representation

• The target shape $S$ is converted into a 3D binary voxel array (0 for background, 1 for the particle).
• The array is surrounded by a double-layered hull of zeros to ensure boundary conditions are met.
• The lattice constant $h$ defines the resolution.

B. Core Algorithm Steps

1. Initial Euclidean Distance Transform (EDT):

   • Compute the EDT ($E$) of the target shape $S$. For every voxel inside the shape, $E$ stores the distance to the nearest background voxel.
   • Local Maxima Detection: Identify local maxima of $E$. These points represent the centers of the largest possible spheres that fit within the shape.
   • Sub-voxel Refinement: To improve precision beyond the voxel grid, the algorithm analyzes the linear slopes of $E$ around local maxima in each coordinate direction ($i, j, k$). It calculates intersection points of these slopes to estimate the sub-voxel coordinates of the true maximum and the corresponding radius.

2. Initial Sphere Generation:

   • Place spheres at the refined sub-voxel maxima with radii derived from the EDT values. This forms the initial multi-sphere representation $\tilde{S}_0$.

3. Iterative Refinement:

   • Compute the EDT ($\tilde{E}$) of the current sphere representation $\tilde{S}$.
   • Calculate a difference field: $E^* = 2E - \tilde{E}$. This field highlights regions where the current sphere approximation is insufficient.
   • Find local maxima of $E^*$ (at sub-voxel precision). These indicate the optimal locations for new spheres to fill gaps.
   • Add new spheres to the set. Their radii are determined by interpolating the original $E$ (not $E^*$) at the new center locations.
   • Constraint: A minimum distance ($\delta_{min}$) is enforced between new and existing spheres to prevent the addition of redundant, tiny spheres that do not significantly improve the fit.

4. Termination Criteria:

   • The iteration stops when a predefined mismatch threshold is met, a maximum number of spheres is reached, or a minimum sphere radius is violated.
   • Geometric Constraints: For applications involving fragmentation or contact with walls, the algorithm can be modified to ensure spheres do not penetrate specific planes by capping their radii.

3. Key Contributions

• Parameter-Free Operation: Unlike previous methods (e.g., the "Clump" algorithm), MSS requires no user-defined tuning parameters (such as grid resolution or overlap factors) other than the termination criteria. This makes it robust and automated.
• Sub-voxel Precision: The algorithm employs a linear interpolation technique to locate sphere centers and radii with sub-voxel accuracy, significantly improving the smoothness of the resulting surface compared to voxel-grid-aligned methods.
• Symmetry Preservation: The algorithm naturally preserves the inherent symmetries of the target shape, avoiding the "spurious" small spheres that often break symmetry in other generators.
• Implementation: MSS is implemented in both Python and C++ and is designed for integration into DEM codes like MercuryDPM.

4. Results and Performance

The authors benchmarked MSS against the Clump algorithm (identified in prior literature as the state-of-the-art open-source generator) using three test cases:

• Simple Object (Ellipsoid):

  • Using 10 spheres, MSS achieved a significantly lower mismatch (Dice-Sørensen coefficient $D \approx 0.06$) compared to Clump ($D \approx 0.10$).
  • MSS preserved the cylindrical symmetry of the ellipsoid, whereas Clump produced an asymmetric, rough surface.
  • Runtime: MSS was roughly 2x faster (1.3s vs 2.7s).

• Complex Object (Human Femur Bone):

  • Using 70 spheres, MSS achieved a mismatch of $D \approx 0.176$ vs. Clump's $D \approx 0.214$.
  • MSS accurately resolved anatomical features (lesser/greater trochanters) and maintained smooth surfaces (femoral head/shaft). Clump generated "bumpy" surfaces and suppressed fine features.
  • Runtime: MSS was 11x faster (1.88s vs 21.58s).

• Systematic Study (Sand Atlas):

  • Tested on 402 real sand grains.
  • Across 5 to 30 spheres, MSS consistently provided lower shape mismatch and significantly lower computational time compared to Clump.

5. Significance

• Computational Efficiency: By achieving higher accuracy with fewer spheres and faster generation times, MSS enables large-scale DEM simulations of complex granular systems that were previously too computationally expensive.
• Physical Consistency: The elimination of artificial surface roughness (spurious small spheres) prevents unphysical behaviors in simulations, such as incorrect friction or rolling resistance.
• Dynamic Simulations: The speed and lack of parameter tuning make MSS ideal for simulations involving particle fragmentation or plastic deformation, where particle shapes change dynamically during the simulation and require rapid re-generation of multi-sphere representations.
• Open Source: The availability of the code facilitates adoption in the scientific community for both technical and geomechanical applications.

In conclusion, MSS represents a significant advancement in particle shape representation for DEM, offering a robust, automated, and highly efficient alternative to existing multi-sphere generators.