parallel verlet ball to ball collision detection handling

Question

I've written a 2d ball to ball particle collision and detection system using Verlet integration. This means my balls are using a "previous position" and "position" (As opposed to a position + a velocity vector).

Then I have a simple algorithm like so:

foreach dynamic_particle_a in dynamic_particles {
  foreach dynamic_particle_b in dynamic_particles {
     if dynamic_particle_a collides with dynamic_particle_b {
       dynamic_particle_a.position += movement
       dynamic_particle_b.position -= movement
     }
  }
}

Edit: movement is just the half the vector need to push dynamic_particle_a out from dynamic_particle_b.

This has be working really well with many particles, looking like a nice flowing fluid.

Now I see there will be a problem here when I try to convert this to be multi-threaded: Any collision causes the particles to be moved, so if the order of collision checks changes (which is likely to occur in a multi-threaded situation), then I have a non-deterministic system.

So my thought was to try to split up the collision detection and the collision resolution in an algorithm like this:

foreach dynamic_particle_a in dynamic_particles {
  foreach dynamic_particle_b in dynamic_particles {
     if dynamic_particle_a collides with dynamic_particle_b {
       dynamic_particle_a.movement += movement
       dynamic_particle_b.movement -= movement
     }
  }
}

foreach dynamic_particle_a in dynamic_particles {
   dynamic_particle_a.position += dynamic_particle_a.movement
   dynamic_particle_a.movement = (0,0)
}

This is giving me results I did not expect. All my balls are colliding and staying outside of each other as expected, but there seems to be quite jittery, and it seems like my balls will just burst upwards with a great amount of force. It is like I have a fluid that has little explosions going off every now and then.

My best guess as to the problem is this: My first algorithm recursively adjusts the balls positions so if there are 3 collisions, the position of the particle is tweaked 3 times. My second algorithm just computes an average movement based on the the 3 collisions and moves the particle once.

I think the recursive nature of the first is allowing the particles to wiggle into cracks and settle nicely. As this is not happening with the second algorithm, it is as if a little change is triggering a cascade of other changes resulting in explosive amounts of energy due to the lack of this wiggling into cracks.

Has any one else ran into a similar problem or have any ideas on what I might be able to try to resolve it? Or is there another algorithm that will work with multi-threading in a deterministic way?

Answer 1

Managing ball-to-ball collisions in a simulation involving multiple interacting objects necessitates an understanding of several fundamental principles, such as collision detection, the application of physical laws (including momentum conservation and restitution), and the efficient resolution of these interactions.

When utilizing the Verlet integration method, a numerical approach for simulating object motion, the process of managing ball-to-ball collisions can be executed in a series of steps:

1. Fundamentals of Verlet Integration Position Update: The Verlet algorithm modifies an object's position by referencing its previous and current positions:

r(t + Δt) = 2r(t) - r(t - Δt) + a(t)Δt²

Where:

r(t) represents the position of the ball at time t, a(t) denotes the acceleration (resulting from gravity, friction, etc.) at time t, Δt signifies the time increment. Velocity Calculation: The velocity can be estimated by the change in position over the time interval:

v(t) = (r(t) - r(t - Δt)) / Δt

2. Collision Detection To ascertain whether two balls collide, it is essential to evaluate if the distance between their centers is less than the sum of their radii:

∥r₁ - r₂∥ < r₁ + r₂

Where:

r₁ and r₂ indicate the positions of balls 1 and 2, r₁ and r₂ represent the radii of the respective balls. If this condition holds true, a collision is confirmed.

3. Collision Response (Elastic Collision) Upon the occurrence of a collision, the velocities of the balls are modified in accordance with the principles of momentum conservation and the coefficient of restitution. The primary steps include:

Relative Velocity: The relative velocity between the balls along the line of contact is expressed as: v_rel = v₁ - v₂

Normal Vector: The unit normal vector n̂ directed from ball 2 to ball 1 is defined as: n̂ = (r₁ - r₂) / ∥r₁ - r₂∥

Impulse Calculation.