examples/sph_gradient_approximation.html

<!doctype html>
<html class="no-js" lang="en">
<head>
	<meta charset="utf-8">
	<style>
		body {font-family: Helvetica, sans-serif;}
		table {background-color:#CCDDEE;text-align:left}
	</style>
	<script type="text/x-mathjax-config">
	  MathJax.Hub.Config({
		extensions: ["tex2jax.js"],
		jax: ["input/TeX", "output/HTML-CSS"],
		tex2jax: {
		  inlineMath: [ ['$','$'], ["\\(","\\)"] ],
		  displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
		  processEscapes: true
		},
		"HTML-CSS": { fonts: ["TeX"] }
	  });
	</script>
	<script type="text/javascript" aync src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.4/MathJax.js"></script>
	<script src="https://cdn.plot.ly/plotly-2.5.1.min.js"></script>
	<title>SPH Gradient Approximation</title>
</head>
<body>
<main>
	<h1 style="text-align:center">SPH Gradient Approximation</h1>
	<table style="align_center;border-radius: 20px;padding: 20px;margin:auto">
		<col width="400"> 
		<col width="400" height="400"> 
		<tr>
			<td>
				<div id="plotOutput" style="width: 600px; height: 600px;border:2px solid #000000;border-radius: 0px;background-color:#EEEEEE"></div>
			</td>
			<td>
				<div id="plotOutput2" style="width: 600px; height: 600px;border:2px solid #000000;border-radius: 0px;background-color:#EEEEEE"></div>
			</td>
		</tr>
		<tr>
		<td><table style="margin:20px">	
			<col width="200" style="padding-right:10px"> 
			<col width="100"> 
			<tr>
				<td><label>Particle radius</label></td>
				<td><span>0.025</span></td>
			</tr>
			<tr>
				<td><label for="supportRadius">Support radius</label></td>
				<td><input onchange="plot.reset()" id="supportRadius" value="0.1" type="input"></td>
			</tr>
			<tr>
				<td><label for="randomOffset">Add random offset</label></td>
				<td><input onchange="plot.reset()" id="randomOffset" type="checkbox"></td>
			</tr>
			<tr>
				<td><label for="kernelGradientCorrection">Use kernel gradient correction</label></td>
				<td><input onchange="plot.plotFunctions()" id="kernelGradientCorrection" type="checkbox"></td>
			</tr>
			<tr>
				<td><label for="showGradX">x-component of gradient</label></td>
				<td><input onchange="plot.reset()" id="showGradX" type="checkbox"></td>
			</tr>
			<tr>
				<td><label for="showGradY">y-component of gradient</label></td>
				<td><input onchange="plot.reset()" id="showGradY" type="checkbox"></td>
			</tr>
		</table></td>
		</tr>

		<tr><td colspan="2">
			<h2>SPH approximation of the gradient of a quadratic function:</h2>
			In this example we approximate the gradient of a quadratic polynomial using the SPH discretization with the cubic spline kernel [KBST19, KBST22]. The left plot shows the particle sampling pattern while the right plot shows the quadratic function, the exact gradient, the SPH gradient approximation, and the error. To compute the SPH approximation the function values are sampled along the red line in the left plot. That means that for each point on the line the neighbors are determined and the SPH difference formula to approximate the gradient is applied [KBST19]:
			$$\langle \nabla f(x,y) \rangle = \sum_j \frac{m_j}{\rho_j} (f(x_j,y_j) - f(x,y)) \nabla W_{ij}$$
			
			Quadratic_function:
			$$f(x,y) = x^2 + \frac14 y^2 - 1$$
			
			Gradient:
			$$\nabla f(x,y) = 2x + \frac12 y$$		
			
			<h3>Kernel gradient correction</h3>
			The SPH gradient approximation of a fluid quantity is error-prone if the particle neighborhood is only partially filled. To consider this in the computation and to make it first-order consistent, the kernel gradient can be corrected by a matrix $\mathbf{L}_i$:
			$$\nabla \tilde {W}_{ij} = L_i \nabla W_{ij},$$
			where 
			$$\mathbf{L}_i = \left ( \sum_j \frac{m_j}{\rho_j} \nabla W_{ij} \otimes (\mathbf{x}_j - \mathbf{x}_i) \right )^{-1}.
			$$
			Note that $\otimes$ denotes the dyadic product of two vectors.
			
			
			<h3>References</h3>
			<ul>
			<li>[KBST19] Dan Koschier, Jan Bender, Barbara Solenthaler, Matthias Teschner.  Smoothed Particle Hydrodynamics for Physically-Based Simulation of Fluids and Solids. Eurographics Tutorial, 2019</li>
			<li>[KBST22] Dan Koschier, Jan Bender, Barbara Solenthaler, Matthias Teschner. A Survey on SPH Methods in Computer Graphics. Computer Graphics Forum, 2022
			</li>
			</ul>
		</td></tr>
	</table>	
	
</main>

<script id="simulation_code" type="text/javascript">
	class Particle 
	{
		constructor (x, y) 
		{
			this.x = x;				// position
			this.y = y;	
			this.density = 0;		// density
		}
	}
		
	class Simulation
	{
		constructor(width, height, sRadius, rand)
		{
			this.particles = [];
			this.particleRadius = 0.025;
			this.supportRadius = sRadius;						// support radius 
			this.density0 = 1000.0;								// rest density of water
			this.diam = 2.0 * this.particleRadius;
			this.mass = this.diam*this.diam*this.density0;		// mass = area * rest density
						
			// constants for kernel computation
			this.kernel_k = 40.0 / (7.0 * (Math.PI*this.supportRadius*this.supportRadius));	  
			this.kernel_l = 240.0 / (7.0 * (Math.PI*this.supportRadius*this.supportRadius));
			this.kernel_0 = this.cubicKernel2D(0);
					
			this.width = width;
			this.height = height;
			this.numParticles = 0;
			
			this.init(rand);
		}
		
		// initialize scene: generate a block of particles 
		init(rand)
		{			
			// create particles  
			let i;
			let j;
			let w = this.width;
			let h = this.height;
			
			// generate a block of fluid particles 
			for (i = 0; i < h; i++) 
			{
				for (j = 0; j < w; j++) 
				{
					this.particles.push(new Particle(
						-w*0.5*this.diam + j*this.diam + this.particleRadius, 
						i*this.diam + this.particleRadius));
					
					if (rand)
					{
						this.particles[this.particles.length-1].x -= 0.01 + Math.random()*0.02;
						this.particles[this.particles.length-1].y -= 0.01 + Math.random()*0.02;
					}
				}
			}
			this.numParticles = this.particles.length;		
							
			// Compute densities
			this.computeDensity();					
		}
		
		// compute the norm of a vector (x,y)
		norm(x, y)
		{
			return Math.sqrt(x*x + y*y);
		}
		
		// Cubic spline kernel 2D
		cubicKernel2D(r)
		{
			let res = 0.0;
			let q = r / this.supportRadius;
			if (q <= 1.0)
			{
				let q2 = q*q;
				let q3 = q2*q;
				if (q <= 0.5)
					res = this.kernel_k * (6.0*q3 - 6.0*q2 + 1.0);
				else
					res = this.kernel_k * (2.0*Math.pow(1.0 - q, 3));
			}
			return res;
		}
		
		// Gradient of cubic spline kernel 2D
		cubicKernel2D_Gradient(rx, ry)
		{
			let res = [0,0];
			let rl = this.norm(rx, ry);
			let q = rl / this.supportRadius;
			if (q <= 1.0)
			{
				if (rl > 1.0e-6)
				{
					let gradq_x = rx * (1.0 / (rl*this.supportRadius));
					let gradq_y = ry * (1.0 / (rl*this.supportRadius));
					if (q <= 0.5)
					{
						res[0] = this.kernel_l*q*(3.0*q - 2.0) * gradq_x;
						res[1] = this.kernel_l*q*(3.0*q - 2.0) * gradq_y;
					}
					else
					{
						let factor = (1.0 - q) * (1.0 - q);
						res[0] = this.kernel_l*(-factor) * gradq_x;
						res[1] = this.kernel_l*(-factor) * gradq_y;
					}
				}
			}
			return res;
		}
		
		// Find all neighbors including the particle itself by a brute force search.
		find_neighbors(x, y)
		{
			let neighbors = [];
			for (let i = 0; i < this.numParticles; i++) 
			{
				let p = this.particles[i];
				let dist2 = (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y);
				let r2 = this.supportRadius * this.supportRadius;
				if (dist2 - r2 < 1.0e-6)
					neighbors.push(i);
			}
			return neighbors;
		}
				
		// compute the density of all particles using the SPH formulation
		computeDensity()
		{
			for (let i = 0; i < this.numParticles; i++) 
			{
				let p_i = this.particles[i];
				let neighbors = this.find_neighbors(p_i.x, p_i.y);
				
				p_i.density = 0.0;
			
				let nl = neighbors.length;
				for(let j=0; j < nl; j++)
				{
					let nj = neighbors[j];
					let p_j = this.particles[nj];
					
					// compute W (xi-xj)
					let Wij = this.cubicKernel2D(this.norm(p_i.x - p_j.x, p_i.y - p_j.y));
					p_i.density += this.mass * Wij;	
				}
			}
		}		
	}
	
	class Plot
	{
		constructor()
		{
		}
		
		reset()
		{
			let sr = parseFloat(document.getElementById('supportRadius').value);
			let r = document.getElementById('randomOffset').checked;	
			delete this.sim;
			this.sim = new Simulation(30, 30, sr, r);
			
			this.plotParticles();
			this.plotFunctions();
		}
		
		quadratic_function(x, y)
		{
			return x*x + 0.25*y*y - 1.0;
		}
		
		gradient(x, y)
		{
			return [2*x, 0.5*y];
		}
		
		plotFunctions()
		{	
			let kernelGradientCorrection = document.getElementById('kernelGradientCorrection').checked;	
			let showGradX = document.getElementById('showGradX').checked;	
			let showGradY = document.getElementById('showGradY').checked;	

			let x = -0.75;
			let y = 0.5;
			let num_steps = 200;
			let xValues = [];
			let yValues_orig = [];
			let gradient_x_orig = [];
			let gradient_y_orig = [];
			let gradient_x_sph = [];
			let gradient_y_sph = [];
			let error = [];
			for (let i = 0; i <= num_steps; i++) 
			{
				xValues.push(x);
				yValues_orig.push(this.quadratic_function(x,y));
				let grad = this.gradient(x,y);
				gradient_x_orig.push(grad[0]);
				gradient_y_orig.push(grad[1]);

				let neighbors = this.sim.find_neighbors(x, y);
				let val_x = 0.0;
				let val_y = 0.0;
				
				// Compute kernel gradient correction matrix
				let L = [[1.0, 0.0], [0.0, 1.0]];
				if (kernelGradientCorrection)
				{
					L = [[0.0, 0.0], [0.0, 0.0]];
					for (let j = 0; j < neighbors.length; j++) 
					{
						let p_j = this.sim.particles[neighbors[j]];
					
						// compute grad W (xi-xj)
						let dx = x - p_j.x;
						let dy = y - p_j.y;
						let gradW = this.sim.cubicKernel2D_Gradient(dx, dy);
						
						L[0][0] -= this.sim.mass / p_j.density * (gradW[0]*dx);
						L[0][1] -= this.sim.mass / p_j.density * (gradW[0]*dy);
						L[1][0] -= this.sim.mass / p_j.density * (gradW[1]*dx);
						L[1][1] -= this.sim.mass / p_j.density * (gradW[1]*dy);
					}
					let det = L[0][0]*L[1][1] - L[0][1]*L[1][0];
					if (Math.abs(det) > 1.0e-6)
						L = [[L[1][1]/det, -L[0][1]/det], [-L[1][0]/det, L[0][0]/det]];
					else 
						L = [[1.0, 0.0], [0.0, 1.0]];
				}

				for (let j = 0; j < neighbors.length; j++) 
				{
					let p_j = this.sim.particles[neighbors[j]];
					
					// compute grad W (xi-xj)
					let gradW = this.sim.cubicKernel2D_Gradient(x - p_j.x, y - p_j.y);
					
					// kernel gradient correction
					let cgradW_x = L[0][0]*gradW[0] + L[0][1]*gradW[1];
					let cgradW_y = L[1][0]*gradW[0] + L[1][1]*gradW[1];
					
					val_x += this.sim.mass / p_j.density * (this.quadratic_function(p_j.x, p_j.y) - this.quadratic_function(x, y)) * cgradW_x;
					val_y += this.sim.mass / p_j.density * (this.quadratic_function(p_j.x, p_j.y) - this.quadratic_function(x, y)) * cgradW_y;
				}
				gradient_x_sph.push(val_x);
				gradient_y_sph.push(val_y);
				let dx = val_x - grad[0];
				let dy = val_y - grad[1];
				error.push(Math.sqrt(dx*dx + dy*dy));
				
				x += 1.5 / num_steps;
				y += 1.0 / num_steps;
			}
			
			var trace_orig = {
			  x: xValues,
			  y: yValues_orig,
			  name: "quadr. fct."
			};
			
			var trace_grad_x_orig = {
			  x: xValues,
			  y: gradient_x_orig,
			  name: "exact grad. x"
			};
			
			var trace_grad_y_orig = {
			  x: xValues,
			  y: gradient_y_orig,
			  name: "exact grad. y"
			};
					
			var trace_x = {
			  x: xValues,
			  y: gradient_x_sph,
			  name: "SPH grad. x"
			};
			
			var trace_y = {
			  x: xValues,
			  y: gradient_y_sph,
			  name: "SPH grad. y"
			};
			
			var trace_error = {
			  x: xValues,
			  y: error,
			  name: "error"
			};
			
			var data = [trace_orig, trace_error];
			
			let yRange = [-0.8, 0.8];
			if (showGradX)
			{
				data.push(trace_grad_x_orig);
				data.push(trace_x);
				yRange = [-1.4,1.6]
			}
			if (showGradY)
			{
				data.push(trace_grad_y_orig);
				data.push(trace_y);
			}
			
			var layout = {
			  title: 'Functions',
			  width: 600,
			  height: 600,
			  xaxis: {
				autorange: [0,2],
			  },
			  yaxis: {
				range: yRange
			  }
			};
			
			Plotly.newPlot('plotOutput2', data, layout);
		}
		
		plotParticles()
		{		
			this.x = [];
			this.y = [];
			this.shapes = [];
			for (let i = 0; i < this.sim.numParticles; i++) 
			{
				let p = this.sim.particles[i];
				this.x.push(p.x);
				this.y.push(p.y);
				this.shapes.push({
				  type: 'circle',
				  xref: 'x',
				  yref: 'y',
				  x0: p.x-0.025,
				  y0: p.y-0.025,
				  x1: p.x+0.025,
				  y1: p.y+0.025,
				  fillcolor: 'rgba(0, 70, 200, 0.7)',
				  line: {
					width: 1,
					color: 'rgba(0, 30, 150, 0.7)'
				  }
				});
			}
			
			var trace1 = {
			  x: this.x,
			  y: this.y,
			  mode: 'text',
			  type: 'scatter',
			};
			
			var trace2 = {
			  x: [-0.75, 0.75],
			  y: [0.5,1.5],
			  line: {
				dash: 'solid',
				color: 'rgba(200,0,0,1)',
				width: 4
			  }
			};
			
			var layout = {
			  title: 'Particles',
			  width: 600,
			  height: 600,
			  xaxis: {
				autorange: [0,2],
			  },
			  yaxis: {
				autorange: [0,2]
			  },
			  showlegend: false,
			  shapes: this.shapes
			};
			
			var data = [trace2, trace1];
			Plotly.newPlot('plotOutput', data, layout);
			Plotly.react('plotOutput', [trace2, trace1], layout);
		}
	}
	
	plot = new Plot();
	plot.reset();
</script>

</body>
</html>