Building the hashed grid data structure requires two steps. The first step computes a hash index for each particle such that all particles in the same grid cell have the same hash index. The second step sorts all particle data by hash index so that the data for all particles in the same hash cell is contiguous in memory.

To compute the hash index, each particle position (x, y, z) is discretized onto a virtual (and infinite) 3D grid by dividing its coordinates by the grid cell size and rounding down to the nearest integer coordinates (i, j, k) = ([x/h], [y/h], [z/h]). These coordinates are then used as input to a hash function that computes a single integer hash index. Our hash function is simple; it computes the integer coordinates modulo the grid size and linearizes the resulting 3D coordinates, as shown in Listing 7.3.1. This simple hash function has the important property that given a hash index, computing the hash indices of neighboring cells is trivial, because neighboring cells in the virtual grid map to neighboring cells in the hash grid (modulo the grid size).

int3 gridPosition(float3 pos, float cellSize)
{

   int3 gridPos;
   gridPos.x = floor(pos.x/cellSize) & (GRID_SIZE – 1);
   gridPos.y = floor(pos.y/cellSize) & (GRID_SIZE – 1);
   gridPos.z = floor(pos.z/cellSize) & (GRID_SIZE – 1);
   return gridPos;
}
int hash(int3 gridPos)
{
   return (gridPos.z * GRID_SIZE + gridPos.y) * GRID_SIZE + gridPos.x;
}

The hash values for each particle are computed in a CUDA C kernel that outputs an array of hash indices and an array of corresponding particle indices. These are then used as arrays of keys and corresponding indices, which we sort using the fast CUDA radix sort of [Satish09]. For each hash grid cell, we also store the sorted indices of the first and last particle in the cell, to enable constant-time queries of the particles in each hash cell. After the key-index pairs are sorted, we use the sorted indices to reorder the particle position and velocity arrays. Reordering the data arrays is important because it ensures efficient, coalesced memory accesses in subsequent CUDA computations.

Using parallel sorting to build this “list of lists” grid structure is more efficient than building it directly (in other words, by appending each particle to a list for each grid cell) in parallel, because we don’t know a priori which cells are occupied and how many particles are in each cell. An advantage of using a radix sort is that multiple non-interacting fluids can be combined within the same virtual grid at low additional cost, because doubling the number of fluids only adds one bit to the sort key length. We simply process the particles of all fluids together in parallel and append the fluid ID above the most significant bit of the hash index. Then when we sort the particles, they will be sorted first by fluid ID and then by hash index. This enables us to do all subsequent steps in the simulation of all fluids in parallel. To reduce sorting cost, we sort using only as many bits as we need to represent our chosen grid resolution, which currently is log₂ N_f + 18 bits (64×64×64 grid), where N_f is the number of fluids.

With the use of a hash, we can handle an unlimited grid. Therefore, the fluid is not confined to a box but can flow anywhere in the scene. Naturally, in a widely dispersed fluid, particles from far-apart cells may hash to the same index. If many non-interacting particles hash to the same index, we will perform unnecessary work to evaluate their Euclidean distance, but in practice this has not been a problem. For more on evaluating hash functions and hash table size, see [Teschner03].

Once the hashed grid is built, it can be used to quickly find all particles near to each particle. Thus, we can evaluate the density and force by finding the cell each particle resides in and iterating over the 27 neighboring cells in 3D. At each neighboring cell, we perform a hash table lookup to find the list of particles in each cell. Using these particles, we can compute the sum of the influences of each neighboring particle, as shown in Listing 7.3.2.

SumOfSupportFunctions(float3 pos, float cellSize)
{

   int3 gridPos = gridPosition(pos, cellSize);
   for (int i = -1; i <= 1; i++)
      for (int j = -1; j <= 1; j++)
         for (int k = -1; k <= 1; k++) {
             gridPosition += int3(i, j, k);
             particles = hashTableLookup(hash(gridPosition))
             foreach particle p in particles {
                sum += supportFunction(pos, p.position);
             }
         }
}

The procedure in Listing 7.3.2 can be applied to both of the steps required to compute the body forces in Equation (1). First, it is used to compute density using the density kernel function. Then, the density is used to compute pressure and viscosity using the pressure and viscosity kernel functions. For details of these kernel functions, see [Müller03].

The four SPH steps shown in Figure 7.3.6 are implemented using one CUDA C kernel each to compute the particle hash, the density, and the force at each particle, plus a radix sort, which is implemented using multiple CUDA C kernels as described in [Satish09], and a kernel that finds the starting and ending indices of particles in each cell and reorders the particle position and velocity arrays using the sorted indices.

The particle hash kernel simply computes the hash index for each particle given its 3D position using the function in Listing 7.3.1. We launch as many GPU threads as there are particles in the scene and compute one hash per thread. After sorting the particles by hash index using the radix sort, we launch another kernel, again with one thread per particle, to reorder the particle position and velocity arrays. This kernel also compares each particle’s hash index against those before and after it in the sorted array. If it is different from the index before it, then we know this is the first particle in a cell, so we store this particle’s index in the sorted array to a “cell starts” array at the cell index. If it is different from the index after it, then it is the end of a cell, so we store its index in a “cell ends” array.

The density and force kernels also process one particle per thread. Each thread runs the procedure given in Listing 7.3.2. The density kernel uses the density support function given in [Müller03] as its support function to compute a scalar density per particle. The force kernel computes two 3D force sums, one using the pressure gradient support function and one using the viscosity Laplacian support function, both given in [Müller03]. The hashTableLookup function in Listing 7.3.2 simply reads the indices at the cell’s index in the cell start and cell end arrays to get a range of particle indices to read from the sorted particle position and velocity arrays.

We make several optimizations to our CUDA C kernels to ensure best performance. First, we pack together the data for all active particle systems or fluids into large batches so that the CUDA kernels can process all particles at once. This improves utilization of the GPU in the presence of multiple small particle systems. We add a small amount of padding between the end of one particle system’s data and the beginning of the next to ensure that each particle system begins on an aligned boundary, and we use structures of arrays (SOA) rather than arrays of structures for the particle data. This means that instead of having an array of particle structures containing particle position, velocity, and other data, we have an array of all particle positions, an array of all velocities, and so on. These optimizations ensure that parallel thread accesses to the data arrays are coalesced by the GPU [NVIDIA09b]. Finally, the density and force kernels bind a texture reference to the data arrays so that the spatially coherent but non-sequential access pattern of these kernels can benefit from the texture cache hardware on the GPU [NVIDIA09b].

The collision phase uses the particle positions and updated velocities from the SPH phase (which includes external accelerations, such as gravity) to compute intersections with scene geometry and rigid bodies and to prevent penetration. The collision algorithm is composed of the following sequence of stages:

Within each stage we can treat particles independently, and therefore we typically use one CUDA thread per particle. The particle data as well as any temporary per-particle storage is laid out as structures of arrays (SOA) for efficient coalesced memory access. As with the SPH stage, in order to improve the utilization of the GPU, each CUDA kernel processes multiple particle systems together in one batch.

The first collision CUDA kernel loads up to two surface constraints from the previous time step for each particle, if available. From the current particle position and velocity, we compute a target position. The target position is projected out of the surface to get a motion path that is not in conflict with the surface the particle is in contact with. The target position is then passed on to the next stage.

Intersection tests for static and dynamic shapes can be handled with the same set of CUDA kernels, treating a static shape as a special case of a dynamic shape that doesn’t move. The collision detection described in this section is therefore executed twice— first for dynamic shapes and then for static shapes.

For each spatially coherent group of particles, we need to find all relevant intersections with all shapes that are provided by the broad phase for this group. To improve execution coherence on the data-parallel GPU architecture, we run a different CUDA kernel for each shape type. Our collision algorithm handles collisions with capsules, convex meshes, and triangle mesh shape types, so we have three shape-specific collision kernels.

Each shape-specific kernel iterates over its shapes by looping over batches of shape data (capsule extents and radii, triangles, or planes depending on shape type) that are loaded by all threads cooperatively from global device memory into fast on-chip shared memory. Then, for each loaded batch, each thread tests one particle for intersection with all shapes in the batch and aggregates the contact information.

In the case of triangle meshes, an additional optimization improves GPU utilization when there are more triangles than particles in the spatial group. Instead of using one thread per particle, it is more efficient to parallelize across triangles (in other words, run one thread per triangle). However, since particles may collide with multiple triangles, we would need to store contact information per particle-triangle pair, which is not memory efficient. Our approach is to perform parallel early-out tests for which the results (one bit per test) can be stored very efficiently. This is done as follows. For each triangle, all particles are investigated to find the ones that potentially collide, ruling out the others with a relatively cheap conservative intersection test. The per-particle contact generation can then skip triangles for which the early-out test had a negative result.

After the dynamic shape collision detection, a CUDA kernel computes a collision response from the aggregated surface contact information and updates particle target positions accordingly. After the static shape collision detection, the collision response kernel is executed again, providing the final particle position.