• Advertisement
Sign in to follow this  

Fluid - Spatial Grid

This topic is 703 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

 

I try to implement an SPH Fluid Simulation based on DirectX 11 Sample from the SDK. I got the N² working, but the Grid/Sort is hard to understand for me. In the example (done by Matthias Müller an Scott Le Grand) from DirectX, the Grid is limited to a 16bit hash so "only" 64K particles. But I need at min 32-Bit and way bigger grid.

 

Here some code of the sample, where he's constructing the Grid. I've no idea what he's doing here and how to extend it to 32bit..

 

EDIT:
And I also need to extend this to 3D positions, as my fluid is not 2D like in the Demo.

//--------------------------------------------------------------------------------------
// Grid Construction
//--------------------------------------------------------------------------------------

// For simplicity, this sample uses a 16-bit hash based on the grid cell and  
// a 16-bit particle ID to keep track of the particles while sorting
// This imposes a limitation of 64K particles and 256x256 grid work
// You could extended the implementation to support large scenarios by using a uint2

float2 GridCalculateCell(float2 position)
{
    return clamp(position * g_vGridDim.xy + g_vGridDim.zw, float2(0, 0), float2(255, 255));
}

unsigned int GridConstuctKey(uint2 xy)
{
    // Bit pack [-----UNUSED-----][----Y---][----X---]
    //                16-bit         8-bit     8-bit
    return dot(xy.yx, uint2(256, 1));
}

unsigned int GridConstuctKeyValuePair(uint2 xy, uint value)
{
    // Bit pack [----Y---][----X---][-----VALUE------]
    //             8-bit     8-bit        16-bit
    return dot(uint3(xy.yx, value), uint3(256*256*256, 256*256, 1));
}
 
unsigned int GridGetKey(unsigned int keyvaluepair)
{
    return (keyvaluepair >> 16);
}

unsigned int GridGetValue(unsigned int keyvaluepair)
{
    return (keyvaluepair & 0xFFFF);
}

//--------------------------------------------------------------------------------------
// Build Grid
//--------------------------------------------------------------------------------------

[numthreads(SIMULATION_BLOCK_SIZE, 1, 1)]
void BuildGridCS( uint3 Gid : SV_GroupID, uint3 DTid : SV_DispatchThreadID, uint3 GTid : SV_GroupThreadID, uint GI : SV_GroupIndex )
{
    const unsigned int P_ID = DTid.x; // Particle ID to operate on
    
    float2 position = ParticlesRO[P_ID].position;
    float2 grid_xy = GridCalculateCell( position );
    
    GridRW[P_ID] = GridConstuctKeyValuePair((uint2)grid_xy, P_ID);
}


//--------------------------------------------------------------------------------------
// Build Grid Indices
//--------------------------------------------------------------------------------------

[numthreads(SIMULATION_BLOCK_SIZE, 1, 1)]
void ClearGridIndicesCS( uint3 Gid : SV_GroupID, uint3 DTid : SV_DispatchThreadID, uint3 GTid : SV_GroupThreadID, uint GI : SV_GroupIndex )
{
    GridIndicesRW[DTid.x] = uint2(0, 0);
}

[numthreads(SIMULATION_BLOCK_SIZE, 1, 1)]
void BuildGridIndicesCS( uint3 Gid : SV_GroupID, uint3 DTid : SV_DispatchThreadID, uint3 GTid : SV_GroupThreadID, uint GI : SV_GroupIndex )
{
    const unsigned int G_ID = DTid.x; // Grid ID to operate on
    unsigned int G_ID_PREV = (G_ID == 0)? g_iNumParticles : G_ID; G_ID_PREV--;
    unsigned int G_ID_NEXT = G_ID + 1; if (G_ID_NEXT == g_iNumParticles) { G_ID_NEXT = 0; }
    
    unsigned int cell = GridGetKey( GridRO[G_ID] );
    unsigned int cell_prev = GridGetKey( GridRO[G_ID_PREV] );
    unsigned int cell_next = GridGetKey( GridRO[G_ID_NEXT] );
    if (cell != cell_prev)
    {
        // I'm the start of a cell
        GridIndicesRW[cell].x = G_ID;
    }
    if (cell != cell_next)
    {
        // I'm the end of a cell
        GridIndicesRW[cell].y = G_ID + 1;
    }
}



Is there someone could help me here?

 

Thanks in advance,

Thomas

Edited by thmfrnk

Share this post


Link to post
Share on other sites
Advertisement
Sorry I am not that math pro, but I need to get it work for vector 3 positions and 32bit indices. I would appreciate any code examples ;)

Share this post


Link to post
Share on other sites

There was a while since I looked at the sample you mention. Basically, they are doing sorting of the particles so that to locate the particles from the same grid cell to process only those which are in the close neighbourhood during the simulation step. It helps them to speed up the process of finding the particles within the smooth length range. Having world space position of the particle and the origin of the grid in the world space you could identify the grid cell position of your particle. Since the grid cell is identified by 3D coordinates it is not easy to sort particles using it as a sorting key. Instead, it could be simply linearized into 1D number and later on used for sorting.

int3 ComputeGridCell(float3 world_space_pos)
{
  float3 grid_space_pos = world_space_pos - g_grid_data.world_space_origin;
  return floor(g_grid_data.rcp_cell_size * grid_space_pos);
}
uint ComputeCellIndex(int3 grid_cell)
{
  return grid_cell.z * g_grid_data.num_cells.x * g_grid_data.num_cells.y + grid_cell.y * g_grid_data.num_cells.x + grid_cell.x;
}

Internally, they are using bitonic sorting to accomplish that. Try googling it or find any General-Purpose GPU-programming book for the details.

If you do not really need their advanced hashing stuff, you can go just with the linearized 1D cell index.

 

Your sort algorithm could accept such struct as an input.

struct GridParticle
{
  uint cell_index;
  uint particle_id;
};
Edited by _void_

Share this post


Link to post
Share on other sites

Hi _void_

 

thank you for your answer. I got it working like you suggested and its workling like a charm. BUT the problem I have now is the Grid-Size. I need to cover an 3D area of about 200x200x20m (and bigger) and to be fast enough I need a cell size of 10cm. In that case my lookup table (where I store the first and last Index of my sorted IndexList), would be about 6GB. Of course only 2% of cells would be filled so a lot of wasted storeage. I know DX12 comes with VolumeTiledRessouces, but I need to stay on DX11. Any idea?

 

thx,

Thomas

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement