Collision free instance painting

[Bird]

give is a try, you should get under 2 ms.

about 1.1 ms

[Julio Jerez]

ah, that's very encouraging.
I now see why the mesh does look so blocky.

for the iso surface to work we need to set of data.
1-the point cloud
2-the implicit surface representing the mesh.

in many cases is possible to get both, but in many other only one of the two is available.

let us say we have both the implicit surface and the sample data, this is the simplest case, but is so trivial that is not interesting. although a case could be made for generation open meshes.

the secund case is we only have the implicit surface, for example a sphere, or any close shape, or any function that can give a density value at any arbitrary point in space. Perlin noise, a 3d texture an so on. this makes the
in this case is very easy to synthetize the point cloud by scanning the mesh a regular interval or at any course granularity like an octree, this is the core based of all those terrain generation engine that we see floating in you tube. This is very simple because is easy to create the sample data.

the much harder case is when we only have the sample points, here is where some implicit surface extraction has to be implemented for creating an implicit surface, but those method are quite hard to implement, Poisson surface smoothing for regular grid is one such case.

in the category fall the simulation of fluids when we do not have the implicitly surface only the point cloud, but the good part is that we can assume that the is we place for box around each sample point, them some boxes will overlap, and form there is a sample point can only be in a corner or at the middle of an edge. So the mesh smoother can only be op half the grid size.

what it means is that for fluid or gasses, the only way to smooth the mesh is by making small.
Also, by using graphics tricks, but in any cases, I am very happy with the result so far.

I now added a object call back so that we can generate smooth mesh for the case where we have the implicit surface. on the weekend I will try to add a simple terrain mesh. see how that goes.

Basically, for a water simulation that the best we can do.

[Bird]

I "think" OpenVDB uses CSG operations on sphere to form the fluids.

https://artifacts.aswf.io/io/aswf/openv ... -1.0.0.pdf

The biggest problem I had in my LightWave plugin that used Flex and OpenVDB was to get realistic thin water meshes, like spilled water on a table top. Here's a demo I made. BTW, the shader splat code that Flex uses in it's demos is opensource and I used it in my LightWave plugin for a "preview" mode like in this video.

https://www.youtube.com/watch?v=XjC-Oet ... eyworksInc

[JoeJ]

The biggest problem I had in my LightWave plugin that used Flex and OpenVDB was to get realistic thin water meshes, like spilled water on a table top.

I never tried to model fluid surface, but i suppose it would work to use a sphere per particle, squished along the density gradient of the combined fluid and table density (which pretty much gives a surface normal).

I do this to model terrain. The image shows some sediment eroded form rock terrain which isn't shown. I use cubes instead spheres, so i also need a tangent direction made from the direction of primary curvature. The cubes are then blended with some exponential blending as shown on Inigo Quilez web site.

sediment.JPG (88.04 KiB) Viewed 3791 times

I tried a lot of things, e.g. using random polyhedra instead boxes which in isolation look much more like a little rock, but i always come back to the simple cubes. Afaik Plato believed rocks would be made from kind of cubic atoms. I'll just adopt that

I hope to hide the visible cube shapes as i turn the surface of this result into a more detailed particle simulation again, add higher frequencies of erosion and destruction over multiple levels, and then i hopefully get natural terrain. But i'm unsure if i can compete the quality of simple and fast heightmap 2D simualtion. If not, i've wasted a lot of time on this stuff... :/

[Julio Jerez]

BTW, the shader splat code that Flex uses in it's demos is opensource and I used it in my LightWave plugin for a "preview" mode like in this video.

ah that's good, because it means the app can use it on their side. so that's one render option.
How many particle on average are you using there?

my goal is that I want to provide a tool that generates a fairly good quality mesh in geometry space that can be used for rendering, all the shader trick I leave it to the end application.

I added the final optimization, and the final lowres generator look like this

Code: Select all

void ndIsoSurface::ndImplementation::ProcessLowResCell(ndIsoCell& cell)
{
   ndInt32 tableIndex = 0;
   for (ndInt32 i = 0; i < 8; ++i)
   {
      tableIndex |= (cell.m_isoValues[i].m_w > m_isoValue) << i;
   }

   ndVector vertlist[12];
   const ndInt32 start = m_edgeScan[tableIndex];
   const ndInt32 edgeCount = m_edgeScan[tableIndex + 1] - start;
   for (ndInt32 i = 0; i < edgeCount; ++i)
   {
      const ndEdge& edge = m_edges[start + i];
      const ndInt32 midPoint = edge.m_midPoint;
      const ndInt32 p0 = edge.m_p0;
      const ndInt32 p1 = edge.m_p1;
      vertlist[midPoint] = InterpolateLowResVertex(cell.m_isoValues[p0], cell.m_isoValues[p1]);
   }
   
   const ndInt32 index = m_triangles.GetCount();
   const ndInt32 faceStart = m_facesScan[tableIndex];
   const ndInt32 faceVertexCount = m_facesScan[tableIndex + 1] - faceStart;
   
   m_triangles.SetCount(index + faceVertexCount * 3);
   ndVector* const triangle = &m_triangles[index];
   for (ndInt32 i = 0; i < faceVertexCount; ++i)
   {
      const ndInt32 j = i * 3;
      const ndInt32 j0 = m_faces[faceStart + i][0];
      const ndInt32 j1 = m_faces[faceStart + i][1];
      const ndInt32 j2 = m_faces[faceStart + i][2];
      
      triangle[j + 0] = vertlist[j0];
      triangle[j + 1] = vertlist[j1];
      triangle[j + 2] = vertlist[j2];
      triangle[j + 0].m_w = ndFloat32(index + j + 0);
      triangle[j + 1].m_w = ndFloat32(index + j + 1);
      triangle[j + 2].m_w = ndFloat32(index + j + 2);
   }
}


All branch less, fully parallelizable and can be converted straight to opencl or a compute shader.
later, when I get the physics solver working, the fluid will be the first conversion to OpenCL and we move from there.

I also made so that is generate a low-resolution mesh and a higher quality mesh, for the later case, the app has the function that generate the density of an arbitrary at a point inside a grid.
this will be the one use for stuff like terrain, and procedural meshes.
Later I will make a demo that use this to make some kind of 3d Terrain with caves and stuff like that.

If you sync, now it can generate a very respectable mesh of about 260k particles.
that's far beyond what the physics will be able to do, in CPU, but it means that the effect can be uses for more than just making surface for volumes of fluid particles.

my solution to the bad quality that you talk about Bill is this.

In CPU the app will be limited to let us say 32 k particle, so only small volume of fluid will be possible.
but on OpenCl, we can go to say 500k particles, so now particle size can be much smaller.

and to solve the course resolution, we will use something like Loop surface subdivision.
https://en.wikipedia.org/wiki/Loop_subdivision_surface

this is like a Camull subdivision, but works on triangle l and cane be code on GPU,
so all the vertex attributes can be extracted from a planal vertex list index list mesh.

stuff like normal interpolation, tri-lineal uv and vertex colors, can all be extracted from there.
In fact, I suspect that the hardware vertex interpolation of DX11, DX12, openGL and vulcan is just
a version of Charles Loop in 1987 surface subdivision surface implemented in silicon and sit in between the vertex shader and fragment shader. more or less like the geometry shader.

but anyway, the point is that we now have a solution for the visual representation, and we can go on with the physics

[Julio Jerez]

I now added the first pass at the sph solver.
Still has ton of bugs, but you can see an explosive number of particle flight appart all over the place.

I need to debug it so is more stable, the one thing the paper do not mention is that those Kerner are the equivalent of very stiff system.

The simulation is very sensitive to small changed in parameters.

I end up taking a 300 fps time step. Or else the acceleration are so huge that the particle fly out of the world.

Anyway there are still plenty of bug fix a tweaking but it start to animate now.

I now need to add some wUI for changing parameter and see how is act visually.

[Julio Jerez]

guys, I know there are still some bugs to hammer out, but I figure I did some stress testing with 256k particles.
and it gets over 30 fps, with for threads.
so all the effort in getting the optimal organization do payoff.
these numbers are better than early GPU implementations.

the mean that the budge for cpu particle could be as high as 64k and the app get it for free.
hikes !!!

[Bird]

Excellent news. I am only getting around 21 fps with 4 threads here on the very latest github but that's still amazing.!

[Julio Jerez]

To decoupled the rendering from the physics, I am using a debug shader to draw each particle at a time.
It is not efficient, but some how my cheap gpu sem to be good at drawing points. But the Rendering is actually blocking the physics. I did not want to spent time optimizing that.
But once I get all the bugs in the physics solver, I will move to the iso surface generator.
And there I estimate from 10 to16 ms gain, so the average should be above 30 for any mid range cpu.

For the kind of work you do, you can probably jack it to millions of particles and do real nice looking rendering at reasonably fps.
The advantage of cpu is that the app gets the mesh and can apply those woderfull water shaders, and even do Ray trace rendering.

Right now my concern is that I am not missing a glaring bug
That can cost lots of performance.

The particle are too bouncy and I think it is because I am missing pairs in the Kerner, which cause a pressure unbalance and the particle move as if they are under lot of turbulence.

I am adding debug code to check that. This are the kind of problems that you can't actually debug because the show when there are lot of element.
Any way it is still work in progress.

[JoeJ]

Nice I also get something like 23 fps at default settings after start.

I wonder, it looks like the simulation is unbounded. The particles expand over all the place and i see no box limiting their simulation domain.
How large is your grid? And how many particles per cell do you have in this setup?

[Julio Jerez]

Nice ....

I wonder, it looks like the simulation is unbounded. The particles expand over all the place and i see no box limiting their simulation domain.
How large is your grid? And how many particles per cell do you have in this setup?

Ah now you come to the the devil is in the detail my friend.
Yes the simulation is unbounded and the is not limit per cell.

The only requirement is that the grid is large than the particle radius. Which I made implicit by having g a funtion that set the grid size to the diameter time 1.5

It is eassy to calculatevthe maximum number of ball of radio r can fit is a cube of size 2 * 1.5* r
And is think is less than 32.
So I have an array set to a max of 32 neighbors per particle.

Then the other parameter, is the size of the aabb of the entire set, that now I have set to a 14 bit in grids per dimensions.
That 2 ^14 * grid size.
So if a grid is say 0.01 of a meter, the about a 200 x 200 x 200 meter^3 volume.
Those spec are more than sufficient for simulation of small volume of fluids.

The reason of using 14 bit, is that it can pack the complete grid record in a 64 bit interger,
Using 20 bit for particle index. And one fir cell home grid indicator.

Using 20 bit for dim and 32 bit for cell, yield a 128 bit cell record which double the memory size, with huge bandwidth cost.

I have it set with a difine that specify large ir small grid.

Maybe if we move to hpu them large grid make sense but for now, to me 1 million particle max, in a 200 ^3 cube volume us good fir small effects.

Those are the local dimension, but the volume can be anywhere in the world.

Later I will place a box limit so that it look nicer, but the unbound presentation is part of the plan.

[Julio Jerez]

One coll thing about, the part that generat the particle neighborly array fast.
Is that there are many different fluid solvers
Variants.

The one I am trying is the very simplistic, that only consider
Pressure and viscosity.
Ignoring diverge and surface tension. This make the particle act too jumpy.

I will complete that, but later we can try different solvers, ther are also solver that implement semi solid bodies. And many kind of deformable objects.

[Julio Jerez]

I too another look and performance, and you guys are correct, I am getting 23 ms as well
this is my timing.

Untitled.png (136.18 KiB) Viewed 3713 times

I think the 30 fps I measure when I have a bug that was no calculation all of the particles per a cell.
the 23 ms I think is a Simpton of our CPUs not having enough level 3 cache, (about 8 meg) and the solver used way a lot more that that for 64k particles, you can see that the total memory is about 640 meg for that little effect (include graphics and physics), for GPU that's reasonable but for CPU that's quite taxing.

the biggest problem is in function AddPairs that is using an atomic. you can see bellow

suspension.png (92 KiB) Viewed 3713 times

you can see that is dominate the entire simulation step, when is not the code does not much more work that the other kernels. that's because of the atomic.
here is the code.

Code: Select all

      void AddPair(ndPairInfo& info, ndInt32 particle0, ndInt32 particle1)
      {
         ndVector p1p0(info.m_posit[particle0] - info.m_posit[particle1]);
         ndFloat32 dist2(p1p0.DotProduct(p1p0).GetScalar());
         if (dist2 < info.m_diameter2)
         {
            dAssert(dist2 >= ndFloat32(0.0f));
            ndFloat32 dist = ndSqrt(dist2);
            {
               ndSpinLock lock(info.m_locks[particle0]);
               ndInt8 count = info.m_pairCount[particle0];
               if (count < 32)
               {
                  info.m_pair[particle0].m_m1[count] = particle1;
                  info.m_distance[particle0].m_dist[count] = dist;
                  info.m_pairCount[particle0] = count + 1;

                  #ifdef D_DEBUG_SOLVER
                  dAssert(!info.m_pairfilter.Find(ndWorkingData::ndPair(particle0, particle1)));
                  info.m_pairfilter.Insert(ndWorkingData::ndPair(particle0, particle1));
                  #endif
               }
            }
         
            {
               ndSpinLock lock(info.m_locks[particle1]);
               ndInt8 count = info.m_pairCount[particle1];
               if (count < 32)
               {
                  info.m_pair[particle1].m_m1[count] = particle0;
                  info.m_distance[particle1].m_dist[count] = dist;
                  info.m_pairCount[particle1] = count + 1;

                  #ifdef D_DEBUG_SOLVER
                  dAssert(!info.m_pairfilter.Find(ndWorkingData::ndPair(particle1, particle0)));
                  info.m_pairfilter.Insert(ndWorkingData::ndPair(particle1, particle0));
                  #endif
               }
            }
         }
      }


atomic read and write are expensive operations, in multithread code, the actually serialize the code.
I will remove that over the weeked. and see if it get better.

[JoeJ]

Then the other parameter, is the size of the aabb of the entire set, that now I have set to a 14 bit in grids per dimensions.
That 2 ^14 * grid size.
So if a grid is say 0.01 of a meter, the about a 200 x 200 x 200 meter^3 volume.
Those spec are more than sufficient for simulation of small volume of fluids.

The reason of using 14 bit, is that it can pack the complete grid record in a 64 bit interger,
Using 20 bit for particle index. And one fir cell home grid indicator.

Using 20 bit for dim and 32 bit for cell, yield a 128 bit cell record which double the memory size, with huge bandwidth cost.

I have it set with a difine that specify large ir small grid.

Maybe if we move to hpu them large grid make sense but for now, to me 1 million particle max, in a 200 ^3 cube volume us good fir small effects.

I'm confused.
Do you mean your grid is 16384^3 cells large? (Which would be too large to fit in mem)
Or something like 32*16*32 cells?

Maybe it makes sense to consider a scrollable grid? So if the player swims, the box of fluid sim goes with him. And we add / remove particles as necessary at the boundary.
Another option would be something like a hash grid for a truly unbounded simulation.

[Julio Jerez]

no, in each dimension is encoded with 14 bits, that 16384

now the particle has a radius. let us say we use a 0.01 for radius. but good for debugging.
for that the minim distance of two no overlapping particles is 2 * r = 0.02

we also need some extra padding to make sure a particle will be smaller than a grid.
I am using on radius so our gid size will be 0.03 of a unit.

our system in one unit is one meter.
this means a fluid volume can spread 16384 * 0.03 = 491.0 meters.
that on each dimension.

that's more than enough for a small volume of 64k particle and we can probably tweak the values.
but for now, I am leaving like that.

basically, there is one coordinate system that is measure in grids that maps each grid dimension from world space to grid space. where a particle in world at location 490 meters, and is at location
16384 - 1 in any dimension. but it is not a solid cube, is a sparce grid.

in the demo the cover a lot because I am using a radius of 0.075
first I was using 0.5 for debug but I found that the physics behave very bad with big particles.

I need to do a dimensional analysis to determine the mass of a particle give it radius, and the fluid density. so that the solve work more or less equal independent of the particle size.

for now I am setting hardcoded values for debug purpose.