betaFeedback

WorksPhysics and Astronomy

A GPU-based Hydrodynamic Simulator with Boid Interactions

Abstract

We present a hydrodynamic simulation system using the GPU compute shaders of DirectX for simulating virtual agent behaviors and navigation inside a smoothed particle hydrodynamical (SPH) fluid environment with real-time water mesh surface reconstruction. The current SPH literature includes interactions between SPH and heterogeneous meshes but seldom involves interactions between SPH and virtual boid agents. The contribution of the system lies in the combination of the parallel smoothed particle hydrodynamics model with the distributed boid model of virtual agents to enable agents to interact with fluids. The agents based on the boid algorithm influence the motion of SPH fluid particles, and the forces from the SPH algorithm affect the movement of the boids. To enable realistic fluid rendering and simulation in a particle-based system, it is essential to construct a mesh from the particle attributes. Our system also contributes to the surface reconstruction aspect of the pipeline, in which we performed a set of experiments with the parallel marching cubes algorithm per frame for constructing the mesh from the fluid particles in a real-time compute and memory-intensive application, producing a wide range of triangle configurations. We also demonstrate that our system is versatile enough for reinforced robotic agents instead of boid agents to interact with the fluid environment for underwater navigation and remote control engineering purposes.

Introduction

Parallel fluid mechanical models interacting with autonomous agents have played a crucial role in microfluidic biochemistry, atomic-level condensed matter quantum magnetohydrodynamics, and deep reinforcement learning. The modeling of self-propelled microbial agents undergoing quantum quorum sensing in bioorganic microfluidic environments involves bacterial agents swimming in massive amounts of molecules, in which the state variables of molecules need to be parallelized using molecular dynamical models. Remotely operated telerobotic agents that navigate in oceans on other celestial bodies, such as Titan or Enceladus, need to have a parallelized computational model of the fluid environment they will be operating in to make better autonomous decisions [1], [2]. Here we consider the problem of computationally modeling the interactions between self-propelled or autonomous boid agents with fluid dynamical environments. Contemporary research in smoothed particle hydrodynamics (SPH) often explores interactions between fluid and heterogeneous meshes, but it rarely delves into the integration of SPH with virtual boid agents. In this context, our work stands out as it not only establishes a robust platform for examining the interactions between distributed virtual boid agents and diverse parallel fluid environments but also extends its applicability to simulate the behavior of agents within molecular-scale environments. By incorporating principles from molecular dynamics into the fluid simulator, we can uncover novel insights into the behaviors and interactions at the microscopic level and nanoscopic level, facilitating a deeper understanding of the underlying molecular mechanisms governing the behaviors of both viscoelastic medium and bioorganic agents. Our research builds a platform

for testing the interaction between distributed virtual boid agents and different parallel fluid environments that can be used to simulate agents’ self-driven or remote-controlled operations. The example uses are shown in Figure 1, Figure 2, Figure 3, Figure 4, etc. Our fluid simulation contains large datasets, such as three-dimensional grids and high-resolution meshes. GPUs offer a significant advantage in processing and manipulating such data due to their high memory bandwidth and ability to efficiently handle large arrays. This allows for faster data transfers and improved overall simulation performance.

The simulation environment including the underwater fluid particles, terrain, marine creatures, etc.

Figure 1. The simulation environment including the underwater fluid particles, terrain, marine creatures, etc.

The underwater particle fluid substratum enclosed in a cavern-shaped terrain.

Figure 2. The underwater particle fluid substratum enclosed in a cavern-shaped terrain.

The SPH fluid particle and boid interactions in our system

Figure 3. The SPH fluid particle and boid interactions in our system.

The blue objects are SPH particles. The yellow objects are boid agents.

Figure 4. The blue objects are SPH particles. The yellow objects are boid agents.

In the simulation of the fluid environment, we are using particles to model the forces between the fluid elements, which is crucial to have parallelization. We decided to use GPU compute shaders of DirectX for this parallelization task. Along with tensor processing units and quantum processing units, graphics processing units utilize their special hardware design for computational acceleration, increasingly used more for tasks outside the rendering pipeline [3]. In our simulator, we assigned one GPU thread per particle in the neighborhood search of the SPH, boid, and marching cubes algorithms. In the integration of the parallel SPH model with the distributed boid model of virtual agents, the system allows for agent-fluid interactions, which involve a higher number of particles than using SPH for fluid particles alone, making parallelization more imperative. The boid-based agents influence the movement of SPH fluid particles, while the forces from the SPH algorithm affect the behavior of the boids, in which the interactions between the SPH particles and boid agents are also parallelized. We trained a rover to navigate towards an underwater target, actively engaging with parallel fluid particles in its path. It has learned to intelligently avoid obstacles by receiving a penalty for collisions, while being rewarded for proximity to the target located on the seafloor. The voxel density value of each cube corner is also computed in parallel, which is constructed from the signed distance field between the cube corner and the weighted average position of nearby neighbors. After obtaining the voxel density values from particle positions that define the fluid’s location, we use the marching cubes algorithm to generate the triangles of the surface that wraps around the particles. The code of our system is located at https://github.com/xi-liu-cs/water.

Background

Lagrangian fluid methods track information of individual particles including their position, velocity, pressure, and density as a function of time. Classical mechanics including conservation of mass and energy are directly applied per particle. The Lagrangian framework possesses difficulty in expression of stresses [4]. Eulerian fluid methods describe the flow velocity field as a function of space and time. Instead of tracking information per particle as in the Lagragian method, the Eulerian method tracks information such as velocity, acceleration of elements at a location of interest in a certain time [5]. Quantum electrodynamical models including the incompressible Schrodinger flow [6] and Gross Pitaevskii equation [7] are also used in Eulerian and Lagrangian fluid simulations.

The smoothed particle hydrodynamics (SPH) method makes use of the fluid elements of the Lagrangian description of flow. The movements of the fluid elements is modeled by Newtonian equations of forces from pressure gradient and body forces. Due to the complicated motion of large nn-body systems, the method assumes that the locations of fluid parcels are randomly distributed based on density [4] [8]. High resolution SPH simulations involves high amount of particles, so parallel algorithms or machine learning methods are used for speedups.

Instead of using smoothed particle hydrodynamics (SPH) for fluid motion, we could use molecular dynamics (MD) models [9]. SPH at the mesoscale deals with larger particles or fluid elements, which are more representative of macroscopic behaviors. MD at the microscale involves modeling individual molecules or atoms, capturing very fine-grained details. Although the SPH method has some difficulty in the imposition of boundary conditions, we apply an opposing damped force whenever a particle reaches a boundary according to Newton’s third law. SPH simulations are computationally less demanding than MD simulations. This means that SPH can simulate larger systems and longer time scales more efficiently, making it suitable for studying phenomena that occur over extended periods or involve large volumes.

Machine learning fluid methods can be used to predict particle attributes to reduce the large computational resources needed in addition to parallel computing speedups. A regression forest can be trained on video data obtained from the position based fluids [10] algorithm to iteratively predict the particle states [11]. The smooth particle networks (SPNets) implement the position based fluids algorithm through a smooth particle convolution (ConvSP) layer that compute pairwise interactions between particles and a signed distance field convolution (ConvSDF) layer to compute interactions between particle and static objects, in which they used the Nvidia Flex [12] fluid simulator to generate the ground truth fluid parameters such as positions and velocities and uses backpropagation and gradient descent to update the fluid parameters iteratively until convergence [13]. Long short term memory networks [14], generative adversarial networks [15], and neural style transfer [16] can be used to perform inference and generate advected field quantities or particle attributes with temporal coherence.

Underwater agents and robotic behaviors in fluid simulations model the interaction and control of robots coupling with water. Starfish soft robot was used in a pipeline embedded with a differentiable simulator to alternate between simulated and real experiments, running system identification and trajectory optimization based on gradients from differentiable simulator in the simulation step, then let robotic hardware to execute the optimized trajectory underwater to collect new data as input to the simulation [17] [18]. SPH can be used to control robotic swarms, in which robots are modeled as particles subject to physical forces, using two layers in the control architecture, the lower SPH layer controls the swarm behavior on a particle basis and upper layer control the macroscopic behavior of the swarm [19].

Boids model the flock motion through group actions and interaction between individual birds’ behaviors in a group to simulate the local perception of individual birds and aerodynamic flight, instead of scripting the path of individual agents [20]. Autonomous robotic fish simulators simulate the swimming motion control and autonomous navigation under the influence of hydrodynamics models [21]. The boids algorithm implemented on the GPU in parallel can optimize the model’s performance, and a grid system can be used to optimize neighbor search [22] and force fields can be utilized to allow for obstacle avoidance [23]. The fluid structure interactions in fish swimming can be simulated with non-linear elastic solids with time varying field of distortions for fish body, and propulsive forces between the solid and fluid for the swimming motions [24].

Reynolds was one of the early pioneers in simulating flocking behavior, particularly in relation to birds [25, 20]. The term "boids" refers to a generalized particle system where each boid represents a particle. Boids adhere to three main principles: collision avoidance (separation), velocity matching (alignment), and flock centering (cohesion). Reynolds described how each boid tracks its own position and velocity, updating its velocity based on these principles using user-defined hyperparameters [26]. Additional behaviors such as obstacle avoidance, fleeing, and pursuit can be achieved by incorporating simulated perception techniques like ray-casting. Viscek proposed an alternative approach that employs self-propelling particles and phase transitions [27]. Modern approaches often combine or utilize variations of these methodologies. To optimize performance, one common technique is positional hashing, which reduces the time complexity of finding nearby neighbors. Reynolds initially used an iterative process to identify neighbors, resulting in quadratic complexity. Positional hashing involves mapping boids’ approximate positions to grid cells, enabling the identification of neighbors within a subset of grid cells around a boid’s current cell [28]. Other known methodologies for spatial hashing include quad/oct-trees [29] and navigation meshes [30].

Governing Equations

The forces acting on a moving fluid element consist of body forces and surface forces, which is modeled in the Navier Stokes equations. The body forces include gravitational, electric, and magnetic forces that act on the volumetric mass of the fluid element. The surface forces act on the surface of the fluid element due to pressure on the surface by outside surrounding fluid, and shear and normal stress distributions acting on the surface [31]. Let ρ\rho be the density, V=(u,v,w)\mathbf{V}=(u,v,w) be the flow velocity, DDt=∂∂t+V⋅∇\frac{D}{Dt}=\frac{\partial}{\partial t}+\mathbf{V}\cdot\nabla be the substantial derivative, pp be the pressure, τ\boldsymbol{\tau} be the shear stress, ff be the body force per unit mass, from Newton’s second law, we obtain

ρDVDt=−∇p+∇⋅τ+ρf(1)\rho\frac{D\mathbf{V}}{Dt}=-\nabla p+\nabla\cdot\boldsymbol{\tau}+\rho f \tag*{(1)}
ρDuDt=∂(ρu)∂t+∇⋅(ρuV)(2)\rho\frac{Du}{Dt}=\frac{\partial(\rho u)}{\partial t}+\nabla\cdot(\rho u\mathbf{V}) \tag*{(2)}
=∂(ρu)∂t+∂(ρu2)∂x+∂(ρuv)∂y+∂(ρuw)∂z(3)=\frac{\partial(\rho u)}{\partial t}+\frac{\partial(\rho u^2)}{\partial x}+\frac{\partial(\rho uv)}{\partial y}+\frac{\partial(\rho uw)}{\partial z} \tag*{(3)}
=−∂p∂x+∂τxx∂x+∂τyx∂y+∂τzx∂z+ρfx(4)=-\frac{\partial p}{\partial x}+\frac{\partial\tau_{xx}}{\partial x}+\frac{\partial\tau_{yx}}{\partial y}+\frac{\partial\tau_{zx}}{\partial z}+\rho f_x \tag*{(4)}
ρDvDt=∂(ρv)∂t+∇⋅(ρvV)(5)\rho\frac{Dv}{Dt}=\frac{\partial(\rho v)}{\partial t}+\nabla\cdot(\rho v\mathbf{V}) \tag*{(5)}
=∂(ρv)∂t+∂(ρuv)∂x+∂(ρv2)∂y+∂(ρvw)∂z(6)=\frac{\partial(\rho v)}{\partial t}+\frac{\partial(\rho uv)}{\partial x}+\frac{\partial(\rho v^2)}{\partial y}+\frac{\partial(\rho vw)}{\partial z} \tag*{(6)}
=−∂p∂y+∂τxy∂x+∂τyy∂y+∂τzy∂z+ρfy(7)=-\frac{\partial p}{\partial y}+\frac{\partial\tau_{xy}}{\partial x}+\frac{\partial\tau_{yy}}{\partial y}+\frac{\partial\tau_{zy}}{\partial z}+\rho f_y \tag*{(7)}
ρDwDt=∂(ρw)∂t+∇⋅(ρwV)(8)\rho\frac{Dw}{Dt}=\frac{\partial(\rho w)}{\partial t}+\nabla\cdot(\rho w\mathbf{V}) \tag*{(8)}
=∂(ρw)∂t+∂(ρuw)∂x+∂(ρvw)∂y+∂(ρw2)∂z(9)=\frac{\partial(\rho w)}{\partial t}+\frac{\partial(\rho uw)}{\partial x}+\frac{\partial(\rho vw)}{\partial y}+\frac{\partial(\rho w^2)}{\partial z} \tag*{(9)}
=−∂p∂z+∂τxz∂x+∂τyz∂y+∂τzz∂z+ρfz(10)=-\frac{\partial p}{\partial z}+\frac{\partial\tau_{xz}}{\partial x}+\frac{\partial\tau_{yz}}{\partial y}+\frac{\partial\tau_{zz}}{\partial z}+\rho f_z \tag*{(10)}

This code is an overview of our parallelized simulation process for particle-based fluid dynamics and agent interactions on the GPU. It employs parallel prefix sum, up sweep, and down sweep methods along with hashed cell indices for efficient neighbor list computation. The code then proceeds to calculate the contributions of neighboring particles and agents to various physical quantities, including density, pressure, and forces, while also considering interactions between boid agents, SPH fluid particles, and reinforcement learning forces. Finally, it updates the positions of particles, boid agents, and cube corners using numerical integration and computes the voxel density values and surface triangles using the marching cubes algorithm, enabling the generation of a detailed fluid mesh representation. Let PP be the set of particles, BB be the set of boid agents, CC be the set of cube corners of marching cubes.

for particle_i ∈ P, boid_j ∈ B, corner_k ∈ C of GPU thread_i,j,k
    find particle_neighbor_list_i, boid_neighbor_list_j,
         corner_neighbor_list_k using the parallel prefix sum, up
         sweep, and down sweep method and parallel sorting of
         hashed cell indices
for particle_i ∈ P of GPU thread_i
    for particle_j ∈ neighbor_list_i
        compute the contribution of particle_j to the density rho_i
        , pressure p_i using the kernel
for particle_i ∈ P of GPU thread_i
    for particle_j ∈ neighbor_list_i
        compute the contribution of particle_j to pressure forces
        , viscosity forces, external forces, and forces
        applied onto fluid particles by boid agents
for particle_i ∈ P, boid_j ∈ B, corner_k ∈ C of GPU thread_i,j,k
    update position of particle_i, boid_j, corner_k using numerical
        integration
for boid_i in boid_agents of GPU thread_i
    for boid_j ∈ boid_neighbor_list_j
        compute contributing forces based on interaction with
        SPH fluid particles, boid-boid interactions, and
        reinforcement learning forces
for cube_corner_i ∈ C of GPU thread_i
    for particle_j ∈ corner_neighbor_list_i
        compute the contribution to the voxel density value based on
        the signed distance field between cube_corner_i and
        particle_j
for cube_corner_i ∈ C of GPU thread_i
    use marching cubes algorithm to generate surface triangles
        that encapsulate the fluid particles

Smoothed Particle Hydrodynamics

Let A(x)A(x) be a continuous compactly supported function. The convolution between two functions ff and gg is defined as (f∗g)(t)=∫−∞∞f(τ)g(t−τ)dτ(f * g)(t) = \int_{-\infty}^{\infty} f(\tau)g(t-\tau)d\tau. Let ϵ∈R+\epsilon\in\mathbb{R}^{+}, the convolution of A(x)A(x) with the Dirac δ\delta distribution is equal to AA itself:

(A∗δ)(r)=∫A(r′)δ(r−r′)dr′(11)(A * \delta)(r) = \int A(r')\delta(r-r')dr' \tag*{(11)}
=lim⁡ϵ→0∫−∞r′−ϵA(r′)δ(r−r′)dr′(12)= \lim_{\epsilon\to0} \int_{-\infty}^{r'-\epsilon} A(r')\delta(r-r')dr' \tag*{(12)}
+∫r′−ϵr′+ϵA(r′)δ(r−r′)dr′(13)+ \int_{r'-\epsilon}^{r'+\epsilon} A(r')\delta(r-r')dr' \tag*{(13)}
+∫r′+ϵ∞A(r′)δ(r−r′)dr′(14)+ \int_{r'+\epsilon}^{\infty} A(r')\delta(r-r')dr' \tag*{(14)}
=lim⁡ϵ→0∫r′−ϵr′+ϵA(r′)δ(r−r′)dr′(15)= \lim_{\epsilon\to0} \int_{r'-\epsilon}^{r'+\epsilon} A(r')\delta(r-r')dr' \tag*{(15)}
=A(r)∫δ(r−r′)dr′(16)= A(r)\int\delta(r-r')dr' \tag*{(16)}
=A(r)(17)= A(r) \tag*{(17)}

Let d∈Zd \in\mathbb{Z}, W:Rd×R+→RW:\mathbb{R}^{d} \times\mathbb{R}^{+} \to\mathbb{R} is kernel function or smoothing kernel

A(r)≈(A∗W)(r)=∫A(r′)W(r−r′,h)dr′(18)A(r) \approx(A * W)(r) = \int A(r')W(r-r',h)dr' \tag*{(18)}

We typically use a distribution that is close to a Gaussian distribution to approximate the Dirac δ\delta distribution. Let WW be a function satisfying ∫W(r)dr=1\int W(r)dr = 1, rr be the center of mass, the smoothed density ρs(r)\rho_s(r) is

ρs(r)=∫W(r−r′)ρ(r′)dr′(19)\rho_s(r) = \int W(r-r')\rho(r')dr' \tag*{(19)}

The fluid quantities are interpolated and spatial derivatives are approximated with finite number of sample positions of adjacent particles. Let F\mathcal{F} be the set containing all point samples, viv_i be the volume of particle ii with ρi=mi/vi\rho_i = m_i/v_i [32], the analytic integral is approximated by a sum over sampling points:

A(ri)=(A∗W)(ri)(20)A(r_i) = (A * W)(r_i) \tag*{(20)}
=∫A(r′)W(ri−r′,h)dr′(21)= \int A(r')W(r_i-r',h)dr' \tag*{(21)}
≈∑j∈FAjW(ri−rj,h)vj(22)\approx\sum_{j \in\mathcal{F}} A_jW(r_i-r_j,h)v_j \tag*{(22)}
=∑j∈FAjW(ri−rj,h)mjmj/vj(23)= \sum_{j \in\mathcal{F}} A_jW(r_i-r_j,h)\frac{m_j}{m_j/v_j} \tag*{(23)}
=∑j∈FAjW(ri−rj,h)mjρj(24)= \sum_{j \in\mathcal{F}} A_jW(r_i-r_j,h)\frac{m_j}{\rho_j} \tag*{(24)}
=∑j∈FAjmjρjW(ri−rj,h)(25)= \sum_{j \in\mathcal{F}} A_j\frac{m_j}{\rho_j}W(r_i-r_j,h) \tag*{(25)}

All field quantities indexed using a subscript denote the field evaluated at the respective position. Aj=A(rj)A_j = A(r_j), Wij=W(ri−rj,h)W_{ij} = W(r_i-r_j,h). Each particle jj contain information of its location rjr_j, mass mjm_j, and field AjA_j. It is optional to storing the density ρj\rho_j since it can be reconstructed from location and mass.

The kernel WW are chosen such that it approximates the Dirac Delta function. The choice of the kernel in this paper is based on a combination of Matthias Muller’s work and experimental work [32]. The kernel WW in a SPH simulation can be represented by the form below, [33]. Let d∈Zd \in\mathbb{Z} be the dimension, f:Rd×R+→Rf:\mathbb{R}^{d} \times\mathbb{R}^{+} \to\mathbb{R} be a function, hh is the kernel’s smoothing length, rr is the center of mass, cc be a scaling factor

W(r,h)=1chd{f(r,h)0≤r≤h0otherwise(26)W(r,h) = \frac{1}{ch^d} \begin{cases} f(r,h) & 0 \le r \le h \\ 0 & \text{otherwise} \end{cases} \tag*{(26)}
Wpoly6(r,h)=31564πh9{(h2−r2)30≤r≤h0otherwise(27)W_{\mathrm{poly6}}(r,h) = \frac{315}{64\pi h^9} \begin{cases} (h^2-r^2)^3 & 0 \le r \le h \\ 0 & \text{otherwise} \end{cases} \tag*{(27)}
Wcubic(r,h)={23−r2+12r30≤r≤116(2−r)31≤r≤20r>2(28)W_{\mathrm{cubic}}(r,h) = \begin{cases} \frac{2}{3}-r^2+\frac{1}{2}r^3 & 0 \le r \le1 \\ \frac{1}{6}(2-r)^3 & 1 \le r \le2 \\ 0 & r > 2 \end{cases} \tag*{(28)}

Pressure and Viscosity

We can substitute the pressure pp term for the continuous compactly supported function AA in the equation A(r)≈∑j∈FAjmjρjW(ri−rj,h)A(\mathbf{r}) \approx\sum_{j\in\mathcal{F}} A_j \frac{m_j}{\rho_j} W(\mathbf{r}_i-\mathbf{r}_j,h) that is derived earlier to obtain

fipressure=−∇p(ri)=−∑jmjpjρj∇W(ri−rj,h)(29)f_i^{\mathrm{pressure}}=-\nabla p(\mathbf{r}_i)=-\sum_j m_j\frac{p_j}{\rho_j}\nabla W(\mathbf{r}_i-\mathbf{r}_j,h) \tag*{(29)}

This force is asymmetric when only two particles interact [32] [33]. One way to symmetrize it is taking the arithmetic mean

fipressure=−∑jmjpi+pj2ρj∇W(ri−rj,h)(30)f_i^{\mathrm{pressure}}=-\sum_j m_j\frac{p_i+p_j}{2\rho_j}\nabla W(\mathbf{r}_i-\mathbf{r}_j,h) \tag*{(30)}

The ideal gas equation of state pi=k(ρi−ρ0)p_i=k(\rho_i-\rho_0) is used to compute the pressure, where kk is a temperature dependent gas constant, ρ0\rho_0 is the rest density [34].

W(r,h)=1chd{f(q)0≤q≤10otherwise(31)W(\mathbf{r},h)=\frac{1}{ch^d} \begin{cases} f(q) & 0\le q\le1\\ 0 & \text{otherwise} \end{cases} \tag*{(31)}
q=∥r∥/h∈R, d∈Z(32)q=\lVert\mathbf{r}\rVert/h\in\mathbb{R},\ d\in\mathbb{Z} \tag*{(32)}
∇Wspiky(r,h)=−30πh4(1−q)2qr(33)\nabla W_{spiky}(\mathbf{r},h)=-\frac{30}{\pi h^4}\frac{(1-q)^2}{q}\mathbf{r} \tag*{(33)}
fipressure=−∑jmjpi+pj2ρj∇Wspiky(ri−rj,h)(34)f_i^{\mathrm{pressure}}=-\sum_j m_j\frac{p_i+p_j}{2\rho_j}\nabla W_{spiky}(\mathbf{r}_i-\mathbf{r}_j,h) \tag*{(34)}

substitute the ideal gas equation for pip_i and pjp_j, and expand the ∇Wspiky\nabla W_{spiky} term

fipressure=∑jmjk(ρi−ρ0)+k(ρj−ρ0)2ρj(30πh4(1−qij)2qrij)(35)f_i^{\mathrm{pressure}}=\sum_j m_j\frac{k(\rho_i-\rho_0)+k(\rho_j-\rho_0)}{2\rho_j}\left(\frac{30}{\pi h^4}\frac{(1-q_{ij})^2}{q}\mathbf{r}_{ij}\right) \tag*{(35)}
=15kπh4∑j∈Nimjρi+ρj−2ρ0ρj(1−qij)2qijrij(36)=\frac{15k}{\pi h^4}\sum_{j\in N_i}m_j\frac{\rho_i+\rho_j-2\rho_0}{\rho_j}\frac{(1-q_{ij})^2}{q_{ij}}\mathbf{r}_{ij} \tag*{(36)}

where qij=∥rij∥/hq_{ij}=\lVert\mathbf{r}_{ij}\rVert/h, rij=ri−rj\mathbf{r}_{ij}=\mathbf{r}_i-\mathbf{r}_j, NiN_i is the neighbor list of particle ii within the smoothing length hh

We can substitute the viscosity term μ∇2v\mu\nabla^2v for the continuous compactly supported function AA in A(r)≈∑j∈FAjmjρjW(ri−rj,h)A(\mathbf{r}) \approx\sum_{j\in\mathcal{F}} A_j \frac{m_j}{\rho_j} W(\mathbf{r}_i-\mathbf{r}_j,h) that is derived earlier to obtain

fiviscosity=μ∇2v(ra)=μ∑jmjvjρj∇2W(ri−rj,h)(37)f_i^{\mathrm{viscosity}}=\mu\nabla^2v(\mathbf{r}_a)=\mu\sum_jm_j\frac{v_j}{\rho_j}\nabla^2W(\mathbf{r}_i-\mathbf{r}_j,h) \tag*{(37)}

Viscosity forces are dependent on velocity differences between particles, so can symmetrize the viscosity forces using velocity differences

Underwater Agent Behaviors

At the start of the simulation, nboid∈Nn_{boid}\in\mathbb{N} boids are initialized in randomized positions around a 3D volume, denoted as the Boid Space. The Boid Space is discretized into gx×gy×gzg_x\times g_y\times g_z grid cells, in which gx,gy,gzg_x,g_y,g_z are number of cells in each dimension. These metrics are user-defined hyper-parameters that can be adjusted to suit the situation. Spatial hashing of any 3D vector position px,y,zp_{x,y,z} within the Boid Space into phx,hy,hzp_{h_x,h_y,h_z} is defined as follows:

phx,hy,hz(px,y,z)={⌊pxlx⋅gx⌋⌊pyly⋅gy⌋⌊pzlz⋅gz⌋(38)p_{h_x,h_y,h_z}(p_{x,y,z})= \begin{cases} \left\lfloor\frac{p_x}{l_x}\cdot g_x\right\rfloor\\ \left\lfloor\frac{p_y}{l_y}\cdot g_y\right\rfloor\\ \left\lfloor\frac{p_z}{l_z}\cdot g_z\right\rfloor \end{cases} \tag*{(38)}

The Boid Grid tracks the number of boids within each grid cell. If obstacles with meshes are present in the simulation, each obstacle’s mesh helps to define a separate Obstacle Grid. The mesh normals of each obstacle are attributed to grid cells in the Obstacle Grid and contribute to obstacle avoidance in boids that are close to or within the same grid cell as these mesh normals.

Boid Motion and Agent Fluid Interaction

Boids have a "visual range" that represents the distance at which the other boids are considered "neighbors". Within the visual range there is a smaller "protection range" wherein boids inside the protection range are considered too close. Neighboring boids in the protection range influence the boid’s Separation behavior; neighbors outside the protection range influence the boid’s Alignment and Cohesion behavior. Obstacles are also "tracked" by each boid as long as they are within the Boid’s visual range and influence the boid’s Obstacle Avoidance behavior. Such behaviors are weighted by hyper-parameters tuned by the user. In a hashed spatial grid setup, the visual and protection ranges can be represented by some set number of grid cells extending outward from the boid’s current grid cell. This range is also defined as a hyper-parameter, adjustable by any user. In our system, the update loop of a boid include these steps:

SPH boid interactions

Figure 5. SPH boid interactions

A SPH particle has higher opacity if it is touched by a boid.

Figure 6. A SPH particle has higher opacity if it is touched by a boid.

  1. Separation: The boid adjusts its velocity vv to move away from any neighbor boids in the protection range based on the position pp differences between the boids within a neighborhood, sepsep is an avoid separation scaler that is a tunable parameter, and protect_rangeprotect\_range is the threshold distance value within which the boids need to fly away from each other.

for all boid_i in parallel do
    close = vec3(0)
    sep = 0
    for boid_j ∈ boid_i.neighbor_list
        d = boid_i.p − boid_j.p
        if (length(d) < protect_range)
            close += d
            sep = clamp(1 − d / protect_range, 0, 1)
            boid_i.v += sep ∗ close
  1. Alignment: The boid adjusts its velocity to match the motion direction of all boids within its visual range. Let vav_a be the average velocity of boids inside the visible range of a particular boid. The visible_rangevisible\_range parameter is the threshold distance value within which each boid attempts to match the velocity of other boids, and matmat is a matching factor that is a tunable parameter.

for all boid_i in parallel do
    v_a = vec3(0)
    count = 0
    for boid_j ∈ boid_i.neighbor_list
        d = boid_i.p − boid_j.p
        if (length(d) < visible_range)
            v_a += boid_j.v
            ++count
        if (count > 0) v_a /= count
        boid_i.v += mat ∗ (v_a − boid_i.v)
  1. Cohesion: The boid adjusts its velocity to move closely to the center of mass among itself and all other boids in the visual range. Let pap_a be the average position of boids inside the visible range of a particular boid, and cencen is the centering factor that is a tunable parameter.

for all boid_i in parallel do
    p_a = vec3(0)
    count = 0
    for boid_j ∈ boid_i.neighbor_list
        d = boid_i.p − boid_j.p
        if (length(d) < visible_range)
            p_a += boid_j.p
            ++count
        if (count > 0) p_a /= count
        boid_i.v += cen ∗ (p_a − boid_i.p)
  1. Edge Avoidance: The boid adjusts its velocity to return into the bounds of the Boid Space if it is outside such bounds.

  1. Speed Limit: The boid’s velocity is clamped within a minimum and maximum speed.

  1. Position update: The boid’s position is updated based on the boid’s updated velocity.

  • Obstacle Avoidance: The boid adjusts its velocity based on the averaged norm vector of each obstacle grid cell within the boid’s visual range. Obstacles in the boid’s protection range are weighed heavier than those in just the visual range.

  • Hash Position Update: The boid updates its hash position and informs the Boid Grid if its hash position has shifted to a new grid cell.

The interaction between the fluid particles and boids involve several aspects: the first aspect is the mechanism for boid motions to influence the fluid particles; the second aspect is the mechanism for fluid particle motions to influence the boid motions. See figure 5, 6. To enable the interaction, the particle struct is defined as the following. The touched_by_boid is an integer counter of the number of boids that are currently inside the neighborhood of a given fluid particle. boid_influence is the cumulative acceleration accounting for the force that each boid in the neighbor list applies to the fluid particle. The cell_index variable represents the cell that the particle belongs to, and index_in_cell represents the index inside the cell that particle the is locating at, neighbor is the count of number of neighbors that is currently found in the neighbor search, in which the neighbor search algorithm is covered in detail in the next section.

Listing 1: Particle structure

struct particle
    float mass, density, pressure, speed;
    float3 position, velocity, acceleration, boid_influence;
    int neighbor, cell_index, index_in_cell, is_boid,
        touched_by_boid;

We have a GPU kernel initialize_particle that initialize the particle positions with a float3 vector with random numbers generated within the bounding box’s boundary, the random number generation is using the exclusive or shift algorithm [35]. To implement the forces that the boids are applying to the fluid particles, we attach a particle to each boid using particles[id.x].position=boids[id.x].positionparticles[id.x].position = boids[id.x].position inside the Euler Cromer integration kernel dispatch. We use an integer is_boid, in which if it is one, this particle is attached to a boid, if it is zero, then this particle is not attached to a boid. During the initialize_particle kernel, we allocate a portion of the particles array to be specifically used as boid attachments through if(id.x<nboid)particles[id.x].isboid=1if(id.x < n_boid)particles[id.x].is_boid = 1. After attaching particles to boids, the motions of the boids from the boid algorithm affects the motion of fluid particles from the SPH algorithm.

Listing 2: Initialize particle

uint s, seed;
float ran()
    s ^= 2747636419u; s *= 2654435769u; s ^= s >> 16;
    s *= 2654435769u; s ^= s >> 16; s *= 2654435769u;
    return s / 4294967295.0;

float r(float a, float b) return a + ran() * (b - a);

#pragma kernel initialize_particle
[numthreads(thread_per_group, 1, 1)]
void initialize_particle(uint3 id : SV_DispatchThreadID)
    if (id.x >= n_particle) return;
    s = seed + id.x;
    let ε > 0;
    particles[id.x].position = (r(x_min + ε,x_max − ε), r(y_min + ε,
        y_max − ε), r(z_min + ε,z_max − ε));
    if(id.x < n_boid) particles[id.x].is_boid = 1;
    else particles[id.x].is_boid = 0;
    particles[id.x].touched_by_boid = 0;
    particles[id.x].boid_influence = float3(0., 0., 0.);

To compute the acceleration, we use the equation for fipressure+fiviscosityf_i^{pressure} + f_i^{viscosity} derived in the earlier sections of pressure and viscosity. To account for the forces applied by the boids onto the particles, we increment the touched_by_boid counter whenever we found another boid inside the neighbor list of the given particle, and accumulate the boid_influence acceleration, which is then integrated in the Euler Cromer kernel dispatch.

Listing 3: Compute acceleration

float3 acceleration(int a, int b)
    float rho_i = particles[a].density,
    rho_j = particles[b].density;

float3 diff_pos = particles[a].position − particles[b].
    position;
diff_vel = particles[a].velocity − particles[b].velocity;
float diff_square = dot(diff_pos, diff_pos);
if(diff_square > radius2 || diff_square == 0) return float3
    (0., 0., 0.);
float q = sqrt(diff_square) / radius,
q2 = 1 − q;
float3 res = mass * q2 / (pi * radius4 * rho_j)
    * (15 * bulk_modulus * (rho_i + rho_j − 2 * rest_density)
    * q2 * diff_pos / q − 40 * viscosity_coefficient * diff_vel)
    ;
if (particles[b].is_boid > 0)
    ++particles[a].touched_by_boid;
    particles[a].boid_influence += res;
return res;

To enable SPH fluid particles to affect the boids, we modify the velocity of the boids to account for the influence of each SPH fluid particle. We used a variable sph_factor which is a tunable factor to control the degree of influence that the SPH fluid particles are affecting the boids, then we used boids[id.x].velocity+=particles[id.x].velocity∗sphfactorboids[id.x].velocity += particles[id.x].velocity * sph_factor to implement this aspect of the interaction. To enable SPH fluid particles to interact with the rover, we apply the same algorithm in which we attach particles to each rover to enable each rover to affect the SPH fluid particles, and we modify the velocity of the rover based on the velocity of SPH fluid particles. We use the robot operating system [36] and Unity machine learning agents library [37] (built-in functions SetReward, EndEpisode, AddObservation, etc) to control the rover motion. The rover have its own camera, separate from the main camera of the simulation. The rover’s initial position is on an island. See Figure 7. We trained the rover to reach an underwater target in which it interacts with the underwater fluid particles and it is trained to find a path that avoids obstacles by applying a penalty whenever the rover collides with an obstacle and applying a reward whenever the agent is close enough to the target at the seafloor, in which we detected the collision through the is_overlap function defined below. Let SS be a set of states, AA be a set of actions, θ\theta be the parameters of a policy πθ\pi_\theta, T∈NT \in\mathbb{N} be the number of time steps, γ∈[0,1)\gamma\in[0,1) be the discount factor. The rover attempts to learn a policy πθ:S×A→R\pi_\theta: S \times A \to\mathbb{R} that maximizes the cumulative discounted reward ∑t=0T−1γtR(St,At)\sum_{t=0}^{T-1}\gamma^t R(S_t,A_t). The rover and the fluid environment engage in a series of discrete time steps, represented as t∈Nt \in\mathbb{N}. At each time step tt, the rover observes the state of the environment, denoted as St∈SS_t \in S, and based on this observation, selects an action At∈A(S)A_t \in A(S). After one time step, as a consequence of its action, the rover receives a numerical reward Rt+1∈RR_{t+1} \in\mathbb{R} and transitions to a new state St+1∈SS_{t+1} \in S.

The rover’s initial location is on an island.

Figure 7. The rover’s initial location is on an island.

Listing 4: Rover behavior

int overlap = 0;
public bool is_overlap() return overlap > 0;
void OnTriggerEnter(Collider other) ++overlap;
void OnTriggerExit(Collider other)
    --overlap;
    if(String.Equals(other.gameObject.name, "Landscape"))
        SetReward(-1.0f);
        EndEpisode();

public override void OnEpisodeBegin()
    transform.position = initial_position;

public override void CollectObservations(VectorSensor sensor)
    sensor.AddObservation(target.localPosition);
    sensor.AddObservation(this.transform.localPosition);

sensor.AddObservation(rigid_body.velocity);

public override void OnActionReceived(ActionBuffers actions)
{
    float dx = actions.ContinuousActions[0],
          dy = actions.ContinuousActions[1],
          dz = actions.ContinuousActions[2];
    transform.position += new Vector3(dx, dy, dz) * Time.
        deltaTime * speed;

    float distance_to_target = Vector3.Distance(this.transform.
        localPosition, target.localPosition);
    if (distance_to_target < 1f)
        SetReward(1f);
        EndEpisode();
    if (is_overlap() || is_outside(this.transform.localPosition))
        SetReward(-1f);
        EndEpisode();
}

Neighborhood Search

If every other particle is considered as the neighbor of a particle, then it has a high time space complexity of O(n2)O(n^2). Therefore, we divide the global problem into smaller parallelizable subproblems, only consider the nearby particles within a small distance as the neighbors of a given particle. The parallel marching cubes algorithm for water mesh construction shares the same parallel neighborhood search algorithm with the SPH and boid algorithms. The parallel marching cubes algorithm extracts the isosurface from voxel density computed from particle density. See Figure 8.

parallel marching cubes

Figure 8. parallel marching cubes

For each particle in a given time, we compute the cell that the particle belongs to. We set the boundaries of the particles with a set bound={min⁡x,max⁡x,min⁡y,max⁡y,min⁡z,max⁡z}bound = \{\min_x, \max_x, \min_y, \max_y, \min_z, \max_z\}. Let (cx,cy,cz)∈Z≥0(c_x,c_y,c_z) \in\mathbb{Z}_{\ge0} be the integer coordinates of the cell that encloses the particle, p∈R3p \in\mathbb{R}^3 be the particle’s position, m=(min⁡x,min⁡y,min⁡z)∈R3m = (\min_x,\min_y,\min_z) \in\mathbb{R}^3 be the minimum positional value of the bounding box, ma=(max⁡x,max⁡y,max⁡z)∈R3ma = (\max_x,\max_y,\max_z) \in\mathbb{R}^3 be the maximum positional value of the bounding box, d∈R≥0d \in\mathbb{R}_{\ge0} be the cell size, we define a function get_cell:R3→Z3get\_cell : \mathbb{R}^3 \to\mathbb{Z}^3

get_cell(p)=⌊p−md⌋=(cx,cy,cz)(39)get\_cell(p) = \left\lfloor\frac{p-m}{d} \right\rfloor= (c_x,c_y,c_z) \tag*{(39)}

We maintain the number of cells for each dimension in dim∈Z3dim \in\mathbb{Z}^3, dim=(ma−m)/ddim = (ma-m)/d. Let max_particles_per_grid∈Z≥0max\_particles\_per\_grid \in\mathbb{Z}_{\ge0} be the maximum number of particles that can be in a given cell at a given time. After obtaining the cell number (cx,cy,cz)(c_x,c_y,c_z) in which the particle belongs to, we compute a hash from this cell number, the result hash_grid_position∈Zhash\_grid\_position \in\mathbb{Z} is a hash that uniquely identifies the particle’s cell, then we use hash_grid_position×max_particles_per_grid+original_valuehash\_grid\_position \times max\_particles\_per\_grid + original\_value as the index into an array hash_gridhash\_grid of size (dimx+dimx(dimy+dimydimz))max_particles_per_grid(dim_x + dim_x(dim_y + dim_y dim_z))max\_particles\_per\_grid that stores all the particles that belong to each grid, in which the original_value∈Zoriginal\_value \in\mathbb{Z} is the current count of neighbors that are recorded for this particular cell. We use a spatial hashing function hash:Z3→Zhash : \mathbb{Z}^3 \to\mathbb{Z} defined by hash(cx,cy,cz)=cx+dimx(cy+dimycz)hash(c_x,c_y,c_z) = c_x + dim_x(c_y + dim_y c_z).

Listing 5: Algorithm compute hash grid

[numthreads(thread_x, thread_y, thread_z)]
void compute_hash_grid(uint3 id : SV_DispatchThreadID)
{
    int original_value = 0;
    hash_grid_position = hash(get_cell(particles[id.x].position)
    );
    InterlockedAdd(hash_grid_tracker[hash_grid_position], 1,
        original_value);
    hash_grid[hash_grid_position * max_particles_per_grid +
        original_value] = id.x;
}

After storing the particle indices (index to query from the particles array) that each cell have into hash_grid in compute_hash_grid function, we compute the neighbor list for each particle. Let position∈R3position \in\mathbb{R}^3 be the position of a given particle, origin_index=⌊(position−m)/d⌋∈Z3origin\_index = \lfloor(position-m)/d\rfloor\in\mathbb{Z}^3. We define a function get_nearby_keyget\_nearby\_key to compute the nearby_key array that stores the hashed one dimensional indices of cells (hash(cx,cy,cz))(hash(c_x,c_y,c_z)) that are near the particle at position. We loop through the 33=273^3 = 27 cells that are near the particle, the center of these 27 cells is the cell that contains this particle.

Listing 6: Algorithm get nearby key

void get_nearby_key(int3 origin_index, float3 position, out int
    nearby_key[27])
int3 nearby_index[27];
int idx = 0;
for (int i = -1; i <= 1; ++i)
    for (int j = -1; j <= 1; ++j)
        for (int k = -1; k <= 1; ++k)
            nearby_index[idx++] = origin_index + int3(i, j,
                k);

for(uint a = 0; a < 27; ++a)
    int3 cell = nearby_index[a];
    if (cell.x < 0 || cell.x >= dimension.x || cell.y < 0 ||
        cell.y >= dimension.y || cell.z < 0 || cell.z >=
        dimension.z)
        nearby_key[a] = -1;
    else
        nearby_key[a] = hash(nearby_index[a]);

We define a function compute_neighbor_list to compute the neighbor indices (index into particles array) for each particle. Let g=⌊(position−m)/d⌋∈Z3g = \lfloor(position-m)/d\rfloor\in\mathbb{Z}^3 be the cell number vector of the cell that contains this particle. We allocate a 27-element integer array gridgrid on the stack to store the hashed one dimensional indices of cells computed from get_nearby_key. In the outer loop ∀i∈[0,27)∩Z\forall i \in[0,27) \cap\mathbb{Z}, we iterate through the 27 possible cells that are considered nearby cells for this particle. In the inner loop ∀j∈[0,hash_grid_tracker[grid[i]])∩Z\forall j \in[0,hash\_grid\_tracker[grid[i]]) \cap\mathbb{Z}, we traverse through every particle in grid ii, since grid ii was computed as a nearby grid relative to the origin particle, every particle in grid ii is considered a potential_neighbor of the origin particle. The index of potential_neighbor is computed as hash_grid[grid[i] ∗ max_particles_per_grid + j] in which it generates the permutation of hash_grid_tracker[grid[i]] particle indices for a fixed grid number grid[i]. Then we calculate the squared Euclidean distance between the potential neighbor with the origin particle. If the distance is less than the smoothing length squared, then we found a neighbor for the origin particle and store the index of the newly found neighbor into neighbor_list.

Listing 7: Algorithm compute neighbor list

[numthreads(thread_group_size, 1, 1)]
void compute_neighbor(uint3 id : SV_DispatchThreadID)
{
    if (id.x >= n_particle) return;
    particles[id.x].neighbor = 0;
    int3 g = get_cell(particles[id.x].position);
    int nearby_cells[27];
    get_nearby_key(g, particles[id.x].position, nearby_cells);
    for (uint i = 0; i < 27; ++i)
        if (nearby_cells[i] == -1) continue;
        for (uint j = 0; j < min(hash_grid_tracker[nearby_cells[i]], max_particles_per_grid); ++j)
        {
            const uint potential_neighbor = hash_grid[nearby_cells[i] * max_particles_per_grid + j];
            if (potential_neighbor == id.x) continue;
            const float3 v = particles[potential_neighbor].position - particles[id.x].position;
            if (dot(v, v) < radius2)
                neighbors[id.x * max_particles_per_grid * 27 + particles[id.x].neighbor++] =
                    potential_neighbor;
        }
}

Neighbor Search with Sorting

The neighbor search with sorting is computed by first computing the partial sum of particle counts in each cell and use this as the starting position of each cell to find the potential neighbors, then record the count of neighbors for each particle, then compute a partial sum on the neighbor counts to find the neighbor offsets for each particle (index into neighbor array to record and query the neighbors for each particle). The partial sum is computed in parallel using the up sweep and down sweep method [38] [39].

The prefix sums operation is a function f:Rn→Rnf : \mathbb{R}^n \to\mathbb{R}^n defined by (a0,a1,…,an−1)↦(a0,(a0⊕a1),…,(a0⊕a1⊕…⊕an−1))(a_0, a_1, \ldots, a_{n-1}) \mapsto(a_0, (a_0 \oplus a_1), \ldots, (a_0 \oplus a_1 \oplus\ldots\oplus a_{n-1})) in which the ⊕\oplus operator is an operation such as addition. The reduce operation is a function g:Rn→Rng : \mathbb{R}^n \to\mathbb{R}^n is defined by (a0,a1,…,an−1)↦(a0⊕a1⊕…⊕an−1)(a_0, a_1, \ldots, a_{n-1}) \mapsto(a_0 \oplus a_1 \oplus\ldots\oplus a_{n-1}) [40].

For each particle, we compute a hash value based on its cell id using spatial hashing. After assigning each particle to a cell, we use counting sort to sort the particles by their hash values. Let cell_index be a field of particle struct that stores the hash cell index of this particle, cell_particle_counts be an array that stores the number of particles in each cell, particle_indices_in_cells be the internal indices of each particle relative to the start of each cell (first particle in this cell have 0, second particle in this cell have 1, ...), cell_offsets be an array containing the starting indices of each cell in the sorted array, which is computed as the cumulative sum of the number of particles in the cells inside and before each cell queried, sort_indices be an array that stores the destination sorted indices sorted by each particle’s one dimensional cell index.

Listing 8: Algorithm count sort particle index

void set_particle_count(particle * particles, uint * cell_particle_counts, uint * particle_indices_in_cells)
{
    uint id = blockIdx.x * blockDim.x + threadIdx.x;
    cell_index = hash(get_cell(particles[id]));
    particle[id].cell_index = cell_index;
    particle_indices_in_cells[id] = atomicAdd(&cell_particle_counts[cell_index], 1);
}

void count_sort_particle_index(uint * cell_offsets, uint * particle_indices_in_cells, uint * sort_indices)
{
    uint id = blockIdx.x * blockDim.x + threadIdx.x,
        cell_index = particles[id].cell_index,
        sort_index = cell_offsets[cell_index] + particle_indices_in_cells[id];
    sort_indices[sort_index] = id;
}

#pragma kernel compute_neighbor_count
[numthreads(thread_group_size, 1, 1)]
void compute_neighbor_count(uint3 id : SV_DispatchThreadID)
{
    if (id.x >= n_particle) return;
    int3 origin_index = get_cell(particles[id.x].position);
    int count = 0;
    for (int x = -1; x < 2; ++x)
        for (int y = -1; y < 2; ++y)
            for (int z = -1; z < 2; ++z)
            {
                int3 cell = origin_index + int3(x, y, z);
                int cell_index = hash(cell);
                cell_count = cell_particle_counts[cell_index];
                cell_start = cell_offsets[cell_index];
                for (int i = cell_start; i < cell_start + cell_count; ++i)
                {
                    float3 diff = particles[sort_indices[i]].position - particles[id.x].position;
                    float square_distance = dot(diff, diff);
                    if (square_distance < radius2)
                        ++count;
                }
            }
    particles[id.x].neighbor = count;
    neighbor_count[id.x] = count;
}

We count the number of particles for each cell using an atomic increment, we perform a parallel prefix sum (scan) to compute each particle’s destination address through cell_offsets[cell_index]+particle_indices_in_cells[id] [41] [42] [43]. We then write the particles to contiguous locations in sort_indices array.

After obtaining the sorted particle indices inside the sort_indices array, we compute the count of neighbors for each particle inside the set of 33=273^3 = 27 neighboring cells of the given particle, after obtaining the neighbor counts inside neighbor_count, we perform another parallel prefix sum (scan) to find the partial sum of neighbor counts and store this partial sum into an array neighbor_offsets [39] [44] [45] [46]. Then we find the indices of all neighbors of all particles and store that into neighbors array. Let count=0count = 0, write_offset=neighbor_offset[id.x]write\_offset = neighbor\_offset[id.x], in which countcount is the current count of neighbors of the given particle whose indices are already stored into the neighbors array. We use an assignment neighbors[write_offset+count]=sort_particle_index[i]neighbors[write\_offset + count] = sort\_particle\_index[i] to store the sorted particle index into the neighbors array. The neighbors array is then used in the computation of the density and forces to query the neighbors of each particle. Our approach avoids recomputation of particle neighbors during computation of the density and acceleration step at the expense of space for storing the neighbor offsets and neighbor indices.

Voxel Density

To perform mesh reconstruction from particles, we need to construct a surface that wraps around the particles given particle positions. The metaball approach is best fit for only a few particles [47]. We instead uses the particle neighborhood information for each cube corner. Let x∈R3x \in\mathbb{R}^3 be a cube corner inside the bounds of the SPH simulation, xˉ∈R3\bar{x} \in\mathbb{R}^3 be the weighted average particle position, rˉ∈R\bar{r} \in\mathbb{R} be the weighted average particle radius. The voxel density function ϕ:R3→R\phi: \mathbb{R}^3 \to\mathbb{R} that we used is

ϕ(x)=∣x−xˉ∣−rˉ(40)\phi(x) = \lvert x - \bar{x} \rvert- \bar{r} \tag*{(40)}
xˉ=∑iwixi,rˉ=∑iwiri(41)\bar{x} = \sum_i w_i x_i,\qquad\bar{r} = \sum_i w_i r_i \tag*{(41)}
wi=k(∣x−xi∣/R)∑jk(∣x−xj∣/R)(42)w_i = \frac{k(\lvert x - x_i\rvert/R)}{\sum_j k(\lvert x - x_j\rvert/R)} \tag*{(42)}

k:R→Rk : \mathbb{R} \to\mathbb{R}, k(s)=(1−s2)3k(s) = (1 - s^2)^3 is the kernel function that we used. R∈RR \in\mathbb{R} is the radius of neighborhood around xx.

Surface reconstruction from particle attributes underwater using marching cubes.

Figure 9. Surface reconstruction from particle attributes underwater using marching cubes. The dark mesh near the middle of the fluid substratum is an underwater cave.

Listing 9: Algorithm compute voxel density

[numthreads(threadx,thready,threadz)]
void compute_density(uint3 id : SV_DispatchThreadID)
    cube_corner_pos = (xmin,ymin,zmin) + id * grid_size ∈ ℝ³
    cube_corner_index = id.x + n_point_per_axis * (id.y +
        n_point_per_axis * id.z) ∈ ℤ
    sum = 0, weight_divisor = 0, weight_multiplier ∈ ℝ
    average_particle_pos = (0,0,0) ∈ ℝ³
    for i ∈ [0, cube_corner_neighbor_tracker[cube_corner_index]]
        neighbor_index = cube_corner_neighbor_list[
            cube_corner_index * max_particles_per_cube + i]
        weight_divisor += kernel(length(cube_corner_pos -
            particles[neighbor_index].position) / radius)
    weight_multiplier = 1 / weight_divisor
    for i ∈ [0, cube_corner_neighbor_tracker[cube_corner_index]]
        neighbor_index = cube_corner_neighbor_list[
            cube_corner_index * max_particles_per_cube + i]
        x = length(cube_corner_pos - particles[neighbor_index].
            position) / radius
        weight_i = weight_multiplier * kernel(x)
        average_particle_pos += weight_i * particles[
            neighbor_index].position
    points[cube_corner_index] = cube_corner_pos
    voxel_density[cube_corner_index] = length(cube_corner_pos -
        average_particle_pos) - particle_size

Marching Cubes

The marching cubes algorithm locates the surface, creates triangles, and compute the normals of the surface for each vertex of the triangles. For each cube, the algorithm

computes the intersection representation between the cube and the surface. The surface intersections are computed by comparing the voxel value at the vertex with the isovalue of the surface. If the voxel value at the vertex is below the isovalue, we assign a one to the cube’s vertex. If the voxel value at the vertex is greater than or equal to the isovalue, we assign a zero to the cube’s vertex.

Listing 10: Algorithm cube index

cube_index = 0;
for (int i = 0; i < 8; ++i)
    if (cube_corner_density[i] < isolevel)
        cube_index |= 1 << i;

Consider the configuration in Figure 10 [48], in which green labels denote edge indices and red labels denote vertex indices, suppose the voxel value at vertex 3 is less than the isovalue and every other vertices have a voxel value greater than the isovalue. By algorithm cube index, we obtain a cube_index=(0∣(1<<3))2=(1000)2=(8)10cube\_index = (0| (1 << 3))_2 = (1000)_2 = (8)_{10}. Then, we use the cube_indexcube\_index as the array index of edge_tableedge\_table, finding that edge_table[8]=(80c)16=(1000 0000 1100)2edge\_table[8] = (80c)_{16} = (1000\,0000\,1100)_2, since its at position 2, 3, 11 are ones, we find that the surface intersects with cube at the edges 2, 3, and 11.

marching cubes

Figure 10. marching cubes

We use linear interpolation to compute the vertex positions that are at the intersecting edges. Let i∈Ri \in\mathbb{R} be the isovalue, p1,p2∈R3p_1,p_2 \in\mathbb{R}^3 be vertices of a intersecting edge, v1,v2v_1,v_2 be voxel values at each vertex, then the vertex position p∈R3p \in\mathbb{R}^3 at the intersecting edge is

p=p1+i−v1v2−v1(p2−p1)(43)p = p_1 + \frac{i-v_1}{v_2-v_1}(p_2-p_1) \tag*{(43)}
Different triangle configurations produced by the parallel marching cubes algorithm

Figure 11. The figures show the different triangle configurations produced by the parallel marching cubes algorithm.

To find the triangle facets from vertex positions of intersecting edges, we use the same cube_indexcube\_index as the array index of triangle_tabletriangle\_table, we find triangle_table[8]={3,11,2,−1,−1,−1,−1,−1,−1,−1,−1,−1,−1,−1,−1,−1}triangle\_table[8] = \{3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1\}. By algorithm triangle construction, we construct the triangle from vertices 3, 11, and 2.

for (int i = 0; triangulation[cube_index][i] != -1; i += 3)
    triangle a;
    a.vertex_a = vertex_list[triangle_table[cube_index][i]];
    a.vertex_b = vertex_list[triangle_table[cube_index][i + 1]];
    a.vertex_c = vertex_list[triangle_table[cube_index][i + 2]];
    triangles.append(a);

Experimental Results

The GPU used to perform the experiments is Nvidia GeForce GTX 1080 with Pascal microarchitecture, integrated RAMDAC, and 60Hz refresh rate. The number of CUDA cores used is 2560 with a 1607 MHz graphics clock, 10.01 Gbps memory data rate, 256-bit memory interface, and 320.32 GB/s memory bandwidth. The total available graphics memory is 24400 MB, dedicated video memory is 8192 MB, and shared system memory is 16208 MB. The CPU used is an Intel Xeon W-2123 Processor with 31.7 GB installed usable RAM and a 3.6 GHz processor base frequency. While the experiments performed mainly use the computational capacity of the GPU, the parallel neighbor search algorithms used involve complex calculations including the up sweep and down sweep method that can be efficiently executed on multicore CPUs, which are well-suited for branching, conditional statements, and irregular data access patterns. CPUs can handle these aspects better than GPUs, which excel at massively parallel, regular computations.

We performed a set of experiments measuring the change of neighbor search time and average number of neighbors per particle in SPH and marching cubes with respect to changes in particle count, grid size, smoothing radius length, and threads per group, in which the results are reported in table 1, 2. We observed that the neighbor search time, marching cubes time, and average number of neighbors per particle increase nonlinearly with respect to increase in particle count. The particle radius is chosen to be 0.5 in the simulation units. The length of the cubic grid is chosen to be approximately four times the particle radius. If the grid size is too big, then a given particle can find too many neighbors, making its iterative forward update very slow. If the grid size is too small, then there are not enough neighbors found for a given particle to enable observable hydrodynamical effects. We also applied neural style transfer per frame using Unity’s Barracuda library in the post-processing stage to the voxel density fluid mesh to complement the surface shading step after the marching cubes stage. See figure 15. The algorithm provides a reasonable fluid-agent interaction prediction in mesoscale, which can deviate from real-world behavior due to unaccounted interactions at the microscopic level, in which molecular dynamical models can be used. For a finer grain simulation, the microfluidic dynamics should involve the modeling of individual molecules of the aqueous solution taking into account intramolecular, intermolecular, supramolecular, van der Waals, electromagnetic, nuclear, and thermal effects and forces.

The assignment of multiple particles to each GPU thread is often done to improve the computational efficiency of simulations. By grouping multiple particles per thread, we can reduce the overhead of thread management and synchronization. However, the optimal number of particles per thread may vary depending on the specific simulation and hardware configuration. Increasing the number of particles per thread could potentially increase the performance of the algorithm by utilizing the GPU’s parallel processing capabilities more effectively, but there’s a trade-off between the number of particles and the memory available on each thread. An excessively large number of particles per thread could lead to memory limitations and reduced performance. Finding the right balance typically involves experimentation and performance profiling to determine the optimal configuration for a given simulation. The utilization of multiple CPUs and GPUs can significantly accelerate the performance of our developed simulator, especially when dealing with complex computational tasks and intricate fluid dynamics simulations. By employing a distributed computing architecture that incorporates multiple CPUs and GPUs, we can parallelize various aspects of the simulation process, effectively dividing the computational workload across these resources. This parallelization approach not only enhances the overall processing power but also enables us to handle larger datasets and perform more detailed simulations, thereby facilitating a more accurate representation of fluid dynamics, particularly at the molecular level. The utilization of multiple CPUs and GPUs empowers the efficient modeling of intricate molecular dynamics and complex forces governing fluid particles and bioorganic agents, facilitating a comprehensive exploration of the underlying molecular mechanisms at the heart of fluidic environments. This advanced computing architecture not only accelerates simulations but also fosters a deeper understanding of the nuanced interactions at the molecular level, enhancing our insights into the intricate dynamics of viscoelastic media and bioorganic systems.

number of particlesgrid sizesmoothing radius lengththreads per groupaverage number of neighbors per particleneighbor search time (seconds)
2.5×1042.5 \times10^{4}2.20.91285210−410^{-4}
5×1045 \times10^{4}2.10.8256782.2×10−42.2 \times10^{-4}
10510^{5}20.75512825×10−45 \times10^{-4}
2×1052 \times10^{5}1.911024843.3×10−33.3 \times10^{-3}
3×1053 \times10^{5}1.8232863.6×10−33.6 \times10^{-3}
7×1057 \times10^{5}1.72.1641034.4×10−34.4 \times10^{-3}
10610^{6}2.32.21281145.1×10−35.1 \times10^{-3}

Table 1. SPH neighbor search time

number of particlesgrid sizethreads per groupmarching cubes time (seconds)percent of connected triangles
10410^{4}2.1645×10−35 \times10^{-3}0%
3×1053 \times10^{5}21283.1×10−23.1 \times10^{-2}70%
4×1054 \times10^{5}1.92563.38×10−23.38 \times10^{-2}85%
5×1055 \times10^{5}1.85124.33×10−24.33 \times10^{-2}95%
7×1057 \times10^{5}2.23210−110^{-1}100%
10610^{6}2641.4×10−11.4 \times10^{-1}100% (less detailed)

Table 2. marching cubes neighbor search time

Currently the smoothed particle hydrodynamics simulation, boids, and the marching cubes voxel density reconstruction pipeline are implemented in the compute shader. For high-fidelity simulation and details in the fluid mesh, we need a high amount of particles. When the particle count is over 10610^{6}, the simulation becomes too slow to be run. In our implementation, the neighbor search with sorting has a lower space-time complexity than the neighbor search without sorting. For the marching cubes aspect, there are many cases the triangles on the particles are only partially constructed, this might be due to too much computation is assigned for each frame and the GPU is not able to finish the computations. Out-of-memory errors were often encountered. When the number of particles is too small, there are not enough triangles constructed from the marching cubes algorithm for the triangles to connect with each other. See figure 8, 9, 11, 13. Distributed multicore CPUs can be used to complement GPUs in our smoothed particle hydrodynamical and interactive boid simulator using the Message Passing Interface (MPI) or Open Multi-Processing (OpenMP) to help mitigate memory limitations and improve simulation speed. When each GPU thread per particle is not assigned with a sufficient amount of work, the cost of communication between threads outweighs the parallelization benefit achieved as compared with assigning the GPU thread with multiple particles or using a distributed multicore CPU hybrid approach. SPH and boid simulations require storing and managing large datasets, including particle positions, densities, pressures, forces, neighbor lists, and other state attributes. CPUs can be better suited for flexible data management tasks, allowing for efficient handling of particle data and reducing the need for constant data transfers between the CPU and GPU memory, which can be a bottleneck. By offloading specific tasks to CPU cores, we can use a hybrid parallelization approach, utilizing both CPU and GPU resources effectively.

The statistics of the rover agent including its cumulative reward, episode length, policy loss, and value loss are

included below in figure 12. The cumulative reward, which represents the average cumulative episode reward across all agents, increased, indicating successful training sessions. The episode length is the mean length of each episode in the environment for all agents. The policy loss, indicating the average loss in the policy function update, decreased, indicating less significant changes in the policy. The value loss, reflecting the mean loss in the value function update, decreased, indicating improved predictive accuracy in estimating state values.

Rover statistics

Figure 12. Rover statistics

Conclusion

We have developed a hydrodynamic simulation system using GPU compute shaders of DirectX that allows us to simulate virtual agent behaviors and navigation within a fluid environment based on smoothed particle hydrodynamics. The boid agents influence the motion of SPH fluid particles, while the forces from the SPH algorithm affect the movement of the boids. Our system performs real time water mesh surface reconstruction using a parallel marching cubes algorithm by calculating the voxel density values of each cube corner based on the signed distance field and then generating triangles that form the surface wrapping around the particles. Our system demonstrates its versatility by supporting reinforced robotic agents in addition to boid agents for underwater navigation and remote control engineering purposes. Our current research has provided valuable insights into the interactions between

parallel marching cubes voxel density reconstruction experiments

Figure 13. parallel marching cubes voxel density reconstruction experiments

SPH boid interactions

Figure 14. SPH boid interactions

neural post processing

Figure 15. neural post processing

self-propelled agents, fluid dynamics, and the integration of smoothed particle hydrodynamics (SPH) with virtual boid agents. Looking ahead, there are several promising avenues for further exploration. As hardware technology advances, it would be beneficial to adapt our simulator to run on more powerful GPUs, such as the A100 or H100, to take advantage of their enhanced capabilities and potentially achieve even more complex and detailed simulations. We also see opportunities for applying our platform to research in microfluidics, nanofluidics, and the bioorganic realm, further extending its scope and relevance in these domains.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

References

  1. [1]P. Davis, Titan overview (2023). URL https://solarsystem.nasa.gov/moons/saturn-moons/titan/overview
  2. [2]J. P. L. NASA, Buoyant rover for under-ice exploration (2015). URL https://www.jpl.nasa.gov/robotics-at-jpl/bruie
  3. [3]T. M. Aamodt, General purpose graphics processor architecture (2018). URL https://picture.iczhiku.com/resource/eetop/WHKdgQhRWGRojBxB.pdf
  4. [4]R. A. Gingold, J. J. Monaghan, Smoothed particle hydrodynamics: theory and application to non-spherical stars. 181 (1977) 375–389. doi:10.1093/mnras/181.3.375.DOI
  5. [5]N. Foster, Realistic animation of liquids (1996).DOI
  6. [6]A. Chern, Schrödinger’s smoke (2016). URL https://cseweb.ucsd.edu/~alchern/projects/SchrodingersSmokeDOI
  7. [7]S. Tsuzuki, Theoretical framework bridging classical and quantum mechanics for the dynamics of cryogenic liquid helium-4 using smoothed-particle hydrodynamics (Dec 2022).DOI
  8. [8]M. Müller, Particle-based fluid simulation for interactive applications (2003). URL https://matthias-research.github.io/pages/publications/sca03.pdf
  9. [9]W. Gunsteren, Computer simulation of molecular dynamics (1990). URL https://web.cs.ucdavis.edu/~koehl/Teaching/ECS129/Reprints/vanGunsteren_MD.pdf
  10. [10]M. Macklin, Position based fluids (2013).DOI
  11. [11]L. Ladicky, Data-driven fluid simulations using regression forests (2015). URL https://people.inf.ethz.ch/sobarbar/papers/Lad15/DatadrivenFluids.pdfDOI
  12. [12]M. Macklin, Unified particle physics for real-time applications (2014).DOI
  13. [13]C. Schenck, D. Fox, Spnets: Differentiable fluid dynamics for deep neural networks (Sep 2018). URL https://arxiv.org/abs/1806.06094
  14. [14]S. Wiëmel, M. Becher, N. Thuerey, Latent-space physics: Towards learning the temporal evolution of fluid flow (Mar 2019). URL https://arxiv.org/abs/1802.10123
  15. [15]X. Xie, E. Frank, M. Chu, N. Thuerey, Tempogan: A temporally coherent, volumetric gan for super-resolution fluid flow (May 2018). URL https://arxiv.org/abs/1801.09710
  16. [16]B. Kim, V. C. Azevedo, M. Gross, B. Solenthaler (May 2020). [link]. URL https://arxiv.org/abs/2005.00803
  17. [18]T. Du, K. Wu, P. Ma, S. Wah, A. Spielberg, D. Rus, W. Matusik, Diffpd: Differentiable projective dynamics (2021). arXiv:2101. 5317.arxiv.org/abs/2101.05917
  18. [19]M. R. Pac, A. M. Erk̆men, I. Erk̆men, Control of robotic swarm behaviors based on smoothed particle hydrodynamics (2007). doi: 10.1109/ROBOT.2007.4399437. URL https://ieeexplore.ieee.org/document/4399437DOI
  19. [20]C. W. Reynolds, Flocks, herds and schools: A distributed behavioral model, SIGGRAPH Comput. Graph. 21 (4) (1987) 25–34. doi: 10.1145/37402.37406. URL https://doi.org/10.1145/37402.37406
  20. [21]J. Liu, H. Hu, A 3d simulator for autonomous robotic fish (2004). URL https://link.springer.com/article/10.1007/s11633-004-0042-5#citeasDOI
  21. [22]C. Reynolds, Big fast crowds on ps3 (2006). URL https://dl.acm.org/doi/pdf/10.1145/1183316.1183333DOI
  22. [23]R. D. Chiara, U. Erra, V. Scarano, M. Tafuri, Massive simulation using gpu of a distributed behavioral model of a flock with obstacle avoidance: Semantic scholar (Jan 1970).
  23. [24]M. Curatolo, L. Teresi, Modeling and simulation of fish swimming with active muscles (2016). URL https://www.sciencedirect.com/science/article/pii/S0022519316302594DOI
  24. [25]C. W. Reynolds, Computer animation with scripts and actors, in: Proceedings of the 9th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’82, Association for Computing Machinery, New York, NY, USA, 1982, p. 289–296. doi:10.1145/800064.801293. URL https://doi.org/10.1145/800064.801293
  25. [26]C. W. Reynolds, et al., Steering behaviors for autonomous characters, 1999.
  26. [27]T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen, O. Shochet, Novel type of phase transition in a system of self-driven particles, Phys. Rev. Lett. 75 (1995) 1226–1229. doi:10.1103/PhysRevLett.75.1226. URL https://link.aps.org/doi/10.1103/PhysRevLett.75.1226DOI
  27. [28]C. Reynolds, Big fast crowds on ps3, in: Proceedings of the 2006 ACM SIGGRAPH Symposium on Videogames, Sandbox ’06, Association for Computing Machinery, New York, NY, USA, 2006, p. 113–121. doi:10.1145/1183316.1183333. URL https://doi.org/10.1145/1183316.1183333
  28. [29]W. Shao, D. Terzopoulos, Autonomous pedestrians, in: Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’05, Association for Computing Machinery, New York, NY, USA, 2005, p. 19–28. doi:10.1145/1073368.1073371. URL https://doi.org/10.1145/1073368.1073371.
  29. [30]M. Kallmann, Navigation meshes and real-time dynamic planning for virtual worlds (2014). URL http://graphics.ucmerced.edu/papers/14-sig-navplan.pdfDOI
  30. [31]J. D. Anderson, Computational Fluid Dynamics: The basics with applications, McGraw-Hill, 2010.
  31. [32]M. Müller, Particle-based fluid simulation for interactive applications (2003). URL https://matthias-research.github.io/pages/publications/sca03.pdf
  32. [33]Bindel, 1 deriving sph - cornell university (2011). URL https://www.cs.cornell.edu/~bindel/class/cs5220-f11/code/sph-derive.pdf
  33. [34]M. Desbrun, Smoothed particles: A new paradigm for animating highly deformable bodies (1996). URL http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-data-parallel-algorithms.pdfDOI
  34. [35]N. Reed, Quick and easy gpu random numbers (2013). URL https://www.reedbeta.com/blog/quick-and-easy-gpu-random-numbers-in-d3d11
  35. [36]M. Quigley, Ros: An open-source robot operating system (2007). URL http://www.robotics.stanford.edu/~ang/papers/icraoss09-ROS.pdf
  36. [37]A. Juliani, Unity: A general platform for intelligent agents (2020). URL https://arxiv.org/abs/1809.02627
  37. [38]M. Imhsen, N. Akinci, M. Becker, M. Teschner, A parallel sph implementation on multi-core cpus (2016).
  38. [39]M. Harris, parallel prefix sum (scan) with cuda (2007). URL https://www.eecs.umich.edu/courses/eecs570/hw/parprefix.pdf
  39. [40]G. Blelloch, Prefix sums and their applications - carnegie mellon university (1993). URL https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf
  40. [41]R. Hoetzlein, Fast fixed radius nearest neighbors: Interactive million particle fluids (2014). URL https://on-demand.gputechconf.com/gtc/2014/presentations/S4117-fast-fixed-radius-nearest-neighbor-gpu.pdf
  41. [42]S. Green, Particle simulation using cuda (2010). URL https://developer.download.nvidia.com/assets/cuda/files/particles.pdf
  42. [43]J. Groß, Fast and efficient nearest neighbor search for particle simulations (2019). URL https://diglib.eg.org/bitstream/handle/10.2312/cgvc20191258/055-063.pdf
  43. [44]S. Band, Compressed neighbor lists for sph (2019).DOI
  44. [45]R. Franklin, Nearest point query on 184,088,599 points in e^3 with a uniform grid (2006). URL https://wrfranklin.org/Research/neartp3/neartp3.pdf
  45. [46]D. Hillis, Data parallel algorithms (1986). URL http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-data-parallel-algorithms.pdfDOI
  46. [47]Y. Zhu, Animating sand as a fluid (2005). URL https://www.cs.ubc.ca/~rbridson/docs/zhu-siggraph05-sandfluid.pdf
  47. [48]P. Bourke, Polygonising a scalar field (1994). URL http://paulbourke.net/geometry/polygonise

Paper details

vlnc:W_kdxa4pth
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents