Any Plans for Liquids?

[Julio Jerez]

It if fast yes, but still not what I expect.
This will be the fallback solution, but I belive we can do better.
I do not really like the idea of splitting the sort into two algorithm.
I believe that is possible to derive a full radix sort that does the entire array.
I develope it on paper now, I will try to code it later.
The goal should be less than 1 ms for 32,000 so far is about 2.
But in any case this is not a bad result.

[Julio Jerez]

ok one more test.

In file ../newton-4.00\sdk\dNewton\ndBodySphFluid.h
the is define //#define D_USED_MERGE_SORT
this can be use to compared the tow sorting algorithm

I complet the Radix sort and is just a little be faster that merge sort at about 2.8 ms
while merge is abpout 3.0 ms.
This is good indication that we do not need to use merge source now.

most Radix sort are implemented use either merge or bitonic source to merge small buckets
my version does not, is a pure Radix.

the good part is that this sort uses 6 digits of 10 bit each, most implementation use 4 digit of 8 bit each, so the inner loop have 6 passes as oppose to 4 in most implementations.
the good knew is that we can optimized that if we keep track of teh digit will significant values.

for example for a fluid simulation most particles are clustered, so each for each particle coordinate the higher digits are usually zero. use this fact is a small way we can reduce teh number of passes for 6 to 3, which makes the Radix sort literally twice as fast. I will try that later.
we are now close to start eth actual physics of teh fluid particles.

Anyway if you see hwo is performs in your systems with and with out the define that will be good.

[Julio Jerez]

and I now added thet Fastest mode with yield a 1.8 ms .

Dave if you are following this, and you have time, It would be interesting to see hwo fast is in your system whi is an 8 cores.

also check if the fans get activated. the expectation is that they do not.

[Bird]

With D_USED_MERGE_SORT defined

1 thread = 4.6 ms
8 thread = 1.9 ms

Without D_USED_MERGE_SORT defined

1 thread = 4.6ms
8 thread = 0.9 ms

GPU: NVIDIA Geforce RTX 2070 Super 8GB
CPU: 8 core Intel i7-9700K@3.60GHz 32GB

[Julio Jerez]

excellent, I have a icore7 7700 which is 4 cores, and I get 1.8 ms.
yours is 8 cores and you got 0.9 ms, the yield seems linear with the cores count
but as the time is reduce then overhead of task switching start to become a significant face.

with these results we can probably budge for 64 thousand particles on a mainstream cpu at real time
My hope is that we can do something like this


this was a hardware demo in 2009 using a vector math coprocessor. and it only does 64000 particles.

[Dave Gravel]

Hi Julio,

I get a bit higher here.
Maybe something is slower with the multithread and amd cpu.

Without D_USED_MERGE_SORT
with 1 thread it play around 6.9 - 7.4 ms
with 2 threads I get 3.5 - 3.6 ms
with 4 threads I get 3.8 - 4.2 ms
with 6 threads I get 4.0 - 4.1 ms
with 8 threads I get 3.6 - 3.7 ms
with 12 threads 3.4 - 3.6 ms
with 14 or 16 threads it stay stable at around 3.5 ms

With D_USED_MERGE_SORT
with 1 thread 7.1 - 7.2 ms
with 2 threads 5.0 - 5.1 ms
with 4 threads 5.2 - 5.4 ms
with 6 threads 5.2 - 5.3 ms
with 8 threads 4.6 - 4.7 ms
with 12 threads 4.7 - 4.8 ms
with 14 threads 4.5 - 4.6 ms It is strange that 14 threads get lower here...
with 16 threads 4.5 - 4.6 ms same here.

[Julio Jerez]

Well it shows better timing than the merge sort.
I added the final optimization that reduces the number of passes from six to three when the upper digit is zero. But some how is not twice as fast.
The reason is that as the time spend in sorting goes down, then the other phase become more dominant.
At this point the sorting is not the dominant part of the algorithm. So I am satisfied.

There is one second part the can literally cut that time by half, but that I leave for last.

This is that as it stand now, the algorithm builds the list of clusters on each update, however this may not be necessary.
Here is where the super sampling take place.
We can building the clusters and the mesh reconstruction once per update, while we do the physics simulation at each sub step. Of course this has to be tested, but if it works. Them all the house keeping can become not the dominate factor.

On the differencence in performance, Dave I think it is because your amd cpu is one of the generation that that each Shiplet share the memory cache. The latest amd solved that issue.
This is one of the problem with algorithms like radix sort, that the access memory in a random locations, as opposed to quick and merge sort that have sequential coherent pattern. But the linear time complexity makes Radix a winner for very large set of data. So we go with radix.

[Bird]

excellent, I have a icore7 7700 which is 4 cores, and I get 1.8 ms.
yours is 8 cores and you got 0.9 ms, the yield seems linear with the cores count
but as the time is reduce then overhead of task switching start to become a significant face.

with these results we can probably budge for 64 thousand particles on a mainstream cpu at real time
My hope is that we can do something like this


this was a hardware demo in 2009 using a vector math coprocessor. and it only does 64000 particles.

I hooked up Flex(GPU based) while I'm waiting and it can handle 64000 particles in around 7 ms. I find it pretty difficult to get good looking results without a serious amount of tweaking.
https://youtu.be/60AJEuwFjUw

[Julio Jerez]

oh nice, we can use that as a standard to compare too.
your GPU was considered high end at the time that was developed.
is that simulation using 64000, particles?

I hope, and I have high expectation, that we can achieve similar results or very close to that using a main stream CPU.

fluid simulation is primarily a volumetric problem, so I do not expect this to be capable of simulation large volume of fluids in real time.
but I do think is can be used for simulation shallow laminar fluids and fluid in a small volumes.
for large volumes maybe off line simulation that is competitive with current GPU implementations.

stuff like bathtub, glass of water, spill or water, small conation that has fluid inside, water facet and stuff liek that. basically stuff where teh fluid is a thing layer of more over a surface.

I also hope our implementation is easier to use, but that in the eye of teh beholder. I guess form their point for view their is the best thing since slice bread and butter.

anyway I now added the core funtionality for the surface reconstruction.
The cool part is that this is not going to be a significant factor in the performance.

right now is can only produce one cell efficiently because I have not added the spatial scanning of the spatial so that it only scan the surface of the particle array, right now it will have to do a volumetric scan.
for that I am thinking and octree or a AABB, I like AABB better because they approximate the shape better. but who knwo maybe for this octree is better.

anyway later I will make display the single particle just to make sure the algorithm is correct.

[Julio Jerez]

hurray, I now have the iso surface show on the screen.

it is a humble beginning so do no bee too hard, the point is to flesh out the comple algorithm and see if it is efficient. so far is show to be very efficient.

the problem now are:
1-the location if offset, the two objects should be at the same location.
so I need to figure out why that is.

I am rendering very big just to see where is going to be so do not let the scare you.
with the iso surface the end client can select the mesh resolution they want.
now I need to write the spatial partition so that it can render clusters of particles.
but all in all, the entire thing is on its way.

edit the offset bug is now fixed.

one for the cool thing about the Iso surface class is that it can be use to generate all find natural looking shapes. I added a Perlin Noise class, and to try it out and made a rolling terrain.
I think this Perlin noise is actually too smooth, I like the original one better, but let us see.

with those two classes we can make terrain that actually have overhangs. but that for a different.

anyway now rendering cluster of particles.

[Julio Jerez]

now I placed three particles, and the result are like I expected.
tow particle are close and teh get wrapped on the same surface segment, the one of the far right get it onw surface segment.

the surface generator can make smith meshes but for that it requires a smooth iso value. for particle it use the position to determine if the surface is either 1.0 (under water) or 0.0 (above water).
with only tow density value, the interpolation can only get the half point across the cell.
but I do no thing this is a big problem since we can add a shader that can apply one of tow level of texelation and that will generate a smooth looking water surface, so I am not worried about that.

One big different between this implementation an dthe nvidia one is that I believe their mesh reconstruction is a screen space one. This much faster in terms of the number of particles to process, since the z buffer does the effect filtering all the invisible particles. but them teh have to inverse project the points to a no homogenies space, and the points lose lots of precision because of the z buffer. That's my biggest problem with image precision algorithms, so I will use the object precision one.

edit:
now I have rendering a stream of drops at a one radius size, and the all coalesce nicely.
maybe the trick we can do for single drop particle is to single the out and texelate just those.
but I am not going to worry about that for now. Graphics systems has many ways to address that

[Bird]

oh nice, we can use that as a standard to compare too.
your GPU was considered high end at the time that was developed.
is that simulation using 64000, particles?

Yes, I used 64000 particles in that test.

now I placed three particles, and the result are like I expected.
tow particle are close and teh get wrapped on the same surface segment, the one of the far right get it onw surface segment

.

Hey, that's excellent progress!

I've used OpenVDB for meshing in the past and I believe they use CSG with some special filters to create a fluid mesh. I don't think it's fast enough for your needs though.

watere_mesh.jpg (154.09 KiB) Viewed 6167 times

[Bird]

One big different between this implementation an dthe nvidia one is that I believe their mesh reconstruction is a screen space one.

That's correct. It's a screen space technique Here's some examples. The first is 64000 particles and the second is 32000 particles

https://youtu.be/DmcbSuK2lWg

[Julio Jerez]

what I take from the video you posted of the nvidia stuff is that it seems 32 and 64k particle can do a decent effect for video games. I am hopeful we can be is the same ball park but in CPU, but let us see.
So far the preliminary test are encouraging and they even point that we might be able to do more, but there are still lot of missing parts. let us keep our hopes high.

Image space algorithm are a curse in disguise of a blessing.
they are good for impressive demos that cover a very small scope, but the do not scale up really.

teh onle thing good the filtering thet you get from rending teh particles as splat to a z buffer, and the collecting the visible points. so the problem reduce for 3d volumetric to a 2d surface problem
but after that every thong is just problems.
1- the z buffer add many, many artifact to tha need to be made up by heurism.
2-the mesh you get is not generic so you are at teh mercy for the implementation.
3- the mesh is position dependent, far away many points just vanish because the splat trick is no
really base of any rationality, so deciding size if a black art.
4-the performance various from hardware to hardware.

those are part for the reason that none of that nvidia stuff doesn't make to games.
they are too stylized and extremally difficult to controll, they are onle good for dgc, e3 and siggraphs demos. as nice as those demos are, in a real application you need to scale to practical dimension, and there you get spills where water drop is teh size of a beach ball.
this is why I say this will be good for small controlled simulation like glass of water, small spills,
small volume of fluid like, maybe some smoke puff and so on.


I have to say that they seem to have made a very nice implementation, so maybe some more technology has been discovered or invented seem teh last time I try stuff like that and is was many year ago. I prefer object precision algorithms anytime, because they are far more accurate

[Dave Gravel]

I think Splatoon from nintendo is pretty much the only game that fully using similar effect.
I'm not sure if they using nvidia or self engine simulation.
I think nintendo have use unreal engine for zelda breath of the wild but i'm not sure 100%.
I have already read something about nintendo using ut4 for the switch.
The effect in Splatoon is good but it don't look like fully simulated and accurate.
Maybe they only using some sort of splatting 2d images.
https://www.youtube.com/watch?v=qN4w5D2tzME