Any Plans for Liquids?

[Julio Jerez]

I do not think is a physical simulation, but whatever it is, it is very cool.
You can see that most stuff is made of thin layers, which made sense to me.
I wonder how the do it thought.

[Bird]

Wow, that was pretty cool!

BTW, Flex's GPU code is closed source but the DirectX and Opengl splat rendering shaders are opensource
https://github.com/NVIDIAGameWorks/FleX

And I found some details how it works ( at least back in 2010 )
http://developer.download.nvidia.com/presentations/2010/gdc/Direct3D_Effects.pdf

But I agree, I think the mesh based solution is a better way to go.

[Julio Jerez]

I now has written on paper my algorithm for making the mesh. it is time proportional to the number of particles, in fact is can be derived to work in time proportinal to clusters of particles.

for example, if we have a set of 32 x 32 x 32 = 32k that's a loop that process the 32k particle,
but if we deride into clusters of 4 x 4 x4, that's 8 x 8 x 8 = 512 cells of clusters.

using four cores, each core will be doing approximately 128 cells!! and that's not even counting the trivially rejected.
according to my estimates the surface reconstruction will be able to handle hundreds of thousands particles.
also all those trivial graphic rejection and occlusion apply.
plus we can also move to GPU.
all in all I am very satisfy with what I see in paper.

this can be used to generate mesh not just for fluids, but also stuff like smoke puff using flow velocity field, fractal terrains stuff like boulders using Perlin noise, anything that we can represent with a point cloud at evenly distributed space, or by an iso surface function.

one particular application I want to give another shot, is cloth simulation with rigid springs.
the code is there in 3.14 but I was disappointed with the mesh reconstruction.
but now we can make the mesh reconstruction with actual thickness. This opens a whole universe of possibilities.

I am more encouraged now that we now have cpus that are competitive with GPU. so I am not going to put so much emphasis on the GPU possibility, and keep focus on accuracy and stability.

[Bird]

That sounds very promising! Can't wait to test it out.

I did one last test using the industry standard OpenVDB to convert 64000 particles to a fluid mesh. OpenVDB is cpu based and on my 8 core machine it takes about 150 ms to convert the particles with the settings I used.

https://youtu.be/BAQR4Zsstmo

[Leadwerks]

Very interesting stuff.

[Leadwerks]

The CPU approach makes sense because a top-of-the-line PC will have about 10-25 spare CPU cores but no spare GPU processing power.

[Leadwerks]

Here is what I have right now. There is no cohesion or collision between particles. It's using a raycast right now, which is why the particles go through the rotating beam at one point. 10,000 particles takes about 12 milliseconds max processing time with four CPU cores, and I can probably improve that a lot. The beam is on a passive hinge and is only spinning from the forces the particles are exerting on it.

[Leadwerks]

Using NewtonCollisionCollide() with a sphere for the particle fixes the problem above, but it is about 10x slower than a raycast.

[Julio Jerez]

are you making each particle a rigid body?
Thats going to be too expansive.
this is one of the reason particle are going to be it own object in 4.0
a general broad phase object pruning and to consider too make thing, teleporting, heterogenous shapes types, different shape sizes, balance and other stuff. so adding so make objects of diffrent sizes just make it slower.

a particle system has few things that can be capitalized upon. For example particles are all equal size.
so you know in advance how many cells they will interact with making is possible to use sort and incremental algorithm.

[Leadwerks]

It's using my own simple physics calculation. I only use NewtonCollisionCollide() or NewtonCollisionRaycast() for the collision. First I do a sphere / AABB intersection test in global space, and then I transform the particle position to the box's space and do another intersection test before calling NewtonCollisionCollide().

[Julio Jerez]

In that case, you can make a big simplification by doing these steps.

1 transform all the particles to the space of the collision shapes.

2 for each particle the collision reducec to a distance calculation between the particle point in the local space of the shape and the shape.


From there you can make optimizations.
For example instead of applying the steps to all particles, you can keep the particle in a grid of regular size, that contain a group of particle.
Let us say a grid of radius 3x the diameter of the particle
Can contain up to 4x * 4x * 4x particles and a dirty flag can be use to id the particle cell.

Now you transform the grids to the space of the collider and call for the distance calculation on teh grid.
the one that pass the test, is the array of potential cell collision.
In a pass, remove the duplicates from the cell array.
Now you get a much reduced set of potential particle collider check.
There is a balance between cell size and particle at which the optimization breaks down.

3 the particle who's distance are below some value are the colliding once. For those you get the normal and apply the impulse calculation to chance the particle velocity.

4 integrate all the particles.


Each one of those step parallelize.

This why you see that most collision in physics libraries particle systems, ask the application to pass the colliders.

[Leadwerks]

Oh yeah, I can easily see how that would work, and it would be very easy to construct some kind of grid or octree for the particles. I actually started something like that when I was trying to implement particle cohesion and repulsion.

[Julio Jerez]

You do not need to build octree. It is a waste. The maintainance is a net lost.
Instead just make a grid that you build dynamically.
In fact it can even be double buffered where you build one while you work on a pre build one.

in one pass you compute the cell in which the center of the particle will fall in.
This generates an unsorted array of n particles each with a three index grid cell.
Then using quick or radix sort, you sort the array by the cell id.

Now you have a sorted array of contiguous runs of particle with the same cell ids.
In one pass you count the runs and the number of particle in each run, and that's your grid array of particles.

Now each cell has a radius and that's your super fat particle that you test distance against the Collider.

For a ten k particles all this is much less than 2 ms even in a single core. But from there you can test against an array of colliders. The rest is all the same.

[JoeJ]

Yes SPHD (smoth particles hydro dynamics) is a big plan fro newton 4

I did not read the thread any further, but i can share some experience.
Recently i have implemented the MLS-MPM method like here: https://github.com/yuanming-hu/taichi_mpm
I have also added the 'NACC' material, which is nice to simulate evolving damage, and for that i took a closer look on this mGPU project: https://github.com/penn-graphics-research/claymore

I use the simulator for offline content generation, but my CPU simulator is surprisingly fast. It seems even faster than the research project using 4 Quadro GPUs.
For 1M particles i need 0,2 seconds for a frame (Ryzen 2700), the research project needs 240 seconds for 100M particles on 4 GPUs.

The only thing i do differently than they do is processing blocks in certain order so write hazards are not possible, so no atomics in inner loop are necessary. It also seems they do sparse grid traversal per particle, while i do it only 8 times per block.

This is a nice project aiming to use MPM for a game in realtime (all sim on CPU):

Performance seems similar. He uses only a uniform grid. (Sparse grid update takes something like 10% of frametime for me.)

So... it seems barely possible (On my CPU his demo is only 15fps instead 30). Assuming GPU gives a speedup of at least 10 it becomes pretty practical. Maybe we can do no water yet, but lava would just work. (Notice: timesteps with MPM have to be small, so simulationg one frame per frame is smooth motion, but no realtime.)

I have little experience with SPH, but MPM has the advantage that no search for neighbor particles is necessary. So maybe that's an interesting alternative for you. It's also possible to combine MPM with global solvers on eulerian grid to enable larger timesteps, but i have not tried this.

BTW, some interesting results i got while optimizing:
I first used glm as math library. After replacing with Sonys SSE lib (which came with Bullet and is the same stuff than yours), i got a speedup of an unbelievable 10. Not sure what's wrong with glm, but maybe MSVC has serious issues with some modern C++. Profiler showed many samples going into glm constructors, but it did not really make sense to me.
Sonys library also has a non simd version, and using this gives a slowdown of only 10%. Seems MSVC is pretty good at auto vectorization.

[JoeJ]

You do not need to build octree. It is a waste. The maintainance is a net lost.

I was surprised it's quite fast and can be multi threaded easily because non obvious reasons:
* Particles rarely leave their current cell, and if so, there mostly is already a cell at their new place.
* It's common to use spares blocks of 4^3 cells. One block ends up having hundreds of particles, but because i do not need to search for neighbors that's no problem.
* For the fluid sim community, 'sparse grid' means octree but subdividing into 4^3 instead just 2^3 children. The high branching facter means you'll only hve 2-4 inner levels of the tree - much less than octree. There even exist 'hardware acceleration' methods utilizing CPU memory page mechanisms to avoid traversal (https://orionquest.github.io/papers/SSPGASS/paper.html), which i did not try or look at in detail.

In practice, only particles that truly generate a new block need special care. I append them to a list using atomic counter and process them in a single thread after the bulk work is done. For 1M Particles, the number of such particles is only about 20 per frame.
In the end, updating the grid takes the same time as the final reordering of particles in memory, and the latter can't be avoided anyways even if using a simple dense grid.

But just telling. Not sure if sparse stuff is worth it for games.