Simulate the dynamics in large particle systems on which external forces acts with elastic collisions in real time

Post Reply
Blackboard_99
Posts: 2
Joined: Wed Jan 27, 2021 10:58 am

Simulate the dynamics in large particle systems on which external forces acts with elastic collisions in real time

Post by Blackboard_99 »

Consider the following example: In a two dimensional plane there are a number N of particles (small circles) on
which several external forces act such as different electrostatic force fields of positive and negative charges.

Using superposition, one could calculate a total attractive force F for each particle at time t,
apply Newton d^2 r/ dt^2 = F/M, and solve the resulting differential equations to determine the current
velocity v and position of each particle.

The particles should never overlap each other during the movement and at the end in their final position.
When a collision between particles takes place, it should perform elastic collisions.

Does bullet have an optimized force simulation and collision detection algorithm to simulate the dynamics in large particle systems N = 10^4-10^6 in real time?
User avatar
drleviathan
Posts: 849
Joined: Tue Sep 30, 2014 6:03 pm
Location: San Francisco

Re: Simulate the dynamics in large particle systems on which external forces acts with elastic collisions in real time

Post by drleviathan »

On a suitable machine I believe Bullet could handle 1e5 rigid spheres. I haven't tried it but this is based on memories of anecdotes I've heard. Dunno about 1e6. Bullet starts to have a measurable performance problem when adding new objects to the world when the number of objects already in the world reaches "several 1e4". So... adding/removing particles in the 1e5 and 1e6 range would start to be problematic when you have a real-time budget.

Note, it is possible for rigid bodies to overlap at the end of the Bullet simulation step. They will be pushed apart in later steps, but if you have a very strict requirement that they do not overlap at all, then Bullet will disappoint.

When it comes to electrostatic forces... ignoring the calculation of the field... Bullet could handle applying the forces with little overhead. However, unless you are clever the force calculation is an NxN problem and will stress your real-time budget at suitably large N.

If the simulation is 2D and only involves spheres then some overhead in the Bullet simulation, inherently linked to its ability to handle 3D and more varying shapes, could be avoided by finding (or writing) a more specialized simulation. What you're describing (soup of interacting charged particles) is a known as a "plasma" in the real world and your simulation might benefit from methods developed by theoretical plasma physicists.
Blackboard_99
Posts: 2
Joined: Wed Jan 27, 2021 10:58 am

Re: Simulate the dynamics in large particle systems on which external forces acts with elastic collisions in real time

Post by Blackboard_99 »

Thx for your reply drleviathan.
On a suitable machine I believe Bullet could handle 1e5 rigid spheres.
Sounds good enough.
Bullet starts to have a measurable performance problem when adding new objects to the world
The initial situation would be that there are already 10^4-10^5 particles in the world. Then only single objects (positive and negative charges that are creating the electrical field) are added one after the other. In total, about 10 objects will be added to the world.
Will there also be problems in this case?
When it comes to electrostatic forces... ignoring the calculation of the field... Bullet could handle applying the forces with little overhead. However, unless you are clever the force calculation is an NxN problem and will stress your real-time budget at suitably large N.

What you're describing (soup of interacting charged particles) is a known as a "plasma" in the real world and your simulation might benefit from methods developed by theoretical plasma physicists.
I have expressed myself unclearly. The 10^4-10^5 particles are only interacting with a field that is created by a maximum of 10 objects. The 10^4-10^5 particles are interacting (elastic collision) with themselves only to prevent them from overlapping. But thx for the hint with the plasma topic.

One important question from my side. You said
Note, it is possible for rigid bodies to overlap at the end of the Bullet simulation step. They will be pushed apart in later steps, but if you have a very strict requirement that they do not overlap at all, then Bullet will disappoint.
So during each integration step (position and velocity changes) it is possible, that the particles are overlapping in the animation. But at the end of the simulation all particles are "overlap free" ?
User avatar
drleviathan
Posts: 849
Joined: Tue Sep 30, 2014 6:03 pm
Location: San Francisco

Re: Simulate the dynamics in large particle systems on which external forces acts with elastic collisions in real time

Post by drleviathan »

The initial situation would be that there are already 10^4-10^5 particles in the world. Then only single objects (positive and negative charges that are creating the electrical field) are added one after the other. In total, about 10 objects will be added to the world.
Will there also be problems in this case?
The cost of adding a new object into the world is O(N). When N is less than 1e4 this cost is negligible for most applications on most hardware. Somewhere in the "multiple 1e4" range people start to notice, and I would expect you to notice it at 1e5. It shouldn't be a problem for you... as long as you aren't constantly adding/removing objects every frame.
So during each integration step (position and velocity changes) it is possible, that the particles are overlapping in the animation. But at the end of the simulation all particles are "overlap free" ?
No, it really is possible for pairs of bodies to overlap at the end of the step. However, Bullet will attempt to push them apart (more or less correctly) in the next step. This usually happens when you assemble a large pile of objects under gravity, or squeeze many objects together between compressing walls. In other words: when there are multiple simultaneous overlaps and a few iterations are not enough to solve them all. In a relatively diffuse sphere-sphere interaction I would expect it to be rare but still possible: three or more fast spheres all hitting a tight corner at the same time.
User avatar
Octavius_Ace
Posts: 20
Joined: Sat Jun 04, 2016 10:34 pm
Location: Edinburgh

Re: Simulate the dynamics in large particle systems on which external forces acts with elastic collisions in real time

Post by Octavius_Ace »

If you can restrict things to sphere/sphere interactions, the collision detection is as simple as it gets: sum of radii squared <= dist between centres squared is a collision. Penetration depth and recovery normal are equally trivial to calculate.
Assuming you have a modern graphics card supporting opengl 3 or higher, you could implement this using a compute shader.
Construct a VBO (opengl data array that you construct in main memory and send only once to the graphics memory)
This would have data for each particle, including an active/inactive state, which you toggle on/off to simulate adding new particles, without the run time cost of sending new VBO data between main and graphics memory.

Just look up tutorials on shader based particle systems, for inspiration/guidance.

If you're on Windows/DirectX, you do the same thing, with MS's equivalent.

The only real challenges will be porting the solver into a shader and getting interactions between particles working, due to the pipelined nature of GPUs. You can address this with multiple passes through a shader or set of shaders and making use of compute workgroups perhaps.

Cheers
Post Reply