Viscoelastic springs for sph particle fluids, original patch by Stephen Whitehorn (chickencoop)

* Viscoelastic springs between the fluid particles can simulate all kinds
  of viscous and elastic substances, such as jelly and honey. This is
  achieved by creating springs dynamically between neighboring particles
  and adjusting their rest length based on stretching/compression.
* This nearly completes the currently intended functionality for particle
  fluids. The last missing thing is a surfacing extraction algorithm,
  which is needed for a proper representation of a sph fluid.
* I also cleaned up and renamed some of the fluid parameters to make the
  ui a bit easier to understand.
* One addition to the patch is an option to use "initial rest length" for
  the springs, which uses the lengths between the particles at the time of
  spring creation as the spring rest lengths instead of interaction radius/2.
  This makes the fluid keep it's original shape better (good for very
  viscoelastic materials), but can create large density differences inside
  the fluid (not really physically correct for a fluid).
* Viscoelastic springs are stored in point cache as extra data.

4 files changed, 235 insertions, 33 deletions

diff --git a/source/blender/blenkernel/BKE_pointcache.h b/source/blender/blenkernel/BKE_pointcache.h
index 68c4177fe3a..a4ce46409a1 100644
--- a/source/blender/blenkernel/BKE_pointcache.h
+++ b/source/blender/blenkernel/BKE_pointcache.h
@@ -32,6 +32,7 @@
 #include "DNA_ID.h"
 #include "DNA_object_force.h"
 #include "DNA_boid_types.h"
+#include "DNA_particle_types.h"
 #include <stdio.h> /* for FILE */
 
 /* Point cache clearing option, for BKE_ptcache_id_clear, before
@@ -110,6 +111,16 @@ static char *ptcache_datastruct[] = {
 	"BoidData" // case BPHYS_DATA_BOIDS:
 };
 
+static char *ptcache_extra_datastruct[] = {
+	"",
+	"ParticleSpring"
+};
+
+static int ptcache_extra_datasize[] = {
+	0,
+	sizeof(ParticleSpring)
+};
+
 typedef struct PTCacheFile {
 	FILE *fp;
 
@@ -149,11 +160,11 @@ typedef struct PTCacheID {
 	void (*read_stream)(PTCacheFile *pf, void *calldata);
 
 	/* copies custom extradata to cache data */
-	int (*write_extra_data)(void *calldata, struct PTCacheMem *pm, int cfra);
+	void (*write_extra_data)(void *calldata, struct PTCacheMem *pm, int cfra);
 	/* copies custom extradata to cache data */
-	int (*read_extra_data)(void *calldata, struct PTCacheMem *pm, float cfra);
+	void (*read_extra_data)(void *calldata, struct PTCacheMem *pm, float cfra);
 	/* copies custom extradata to cache data */
-	int (*interpolate_extra_data)(void *calldata, struct PTCacheMem *pm, float cfra, float cfra1, float cfra2);
+	void (*interpolate_extra_data)(void *calldata, struct PTCacheMem *pm, float cfra, float cfra1, float cfra2);
 
 	/* total number of simulated points (the cfra parameter is just for using same function pointer with totwrite) */
 	int (*totpoint)(void *calldata, int cfra);
diff --git a/source/blender/blenkernel/intern/particle.c b/source/blender/blenkernel/intern/particle.c
index 26f96d0c304..279190b9f9c 100644
--- a/source/blender/blenkernel/intern/particle.c
+++ b/source/blender/blenkernel/intern/particle.c
@@ -561,6 +561,9 @@ void psys_free(Object *ob, ParticleSystem * psys)
 		BLI_freelistN(&psys->targets);
 
 		BLI_kdtree_free(psys->tree);
+ 
+		if(psys->fluid_springs)
+			MEM_freeN(psys->fluid_springs);
 
 		pdEndEffectors(&psys->effectors);
 
diff --git a/source/blender/blenkernel/intern/particle_system.c b/source/blender/blenkernel/intern/particle_system.c
index 3534a7dba37..fac79270bc1 100644
--- a/source/blender/blenkernel/intern/particle_system.c
+++ b/source/blender/blenkernel/intern/particle_system.c
@@ -54,6 +54,7 @@
 #include "DNA_ipo_types.h" // XXX old animation system stuff... to be removed!
 #include "DNA_listBase.h"
 
+#include "BLI_edgehash.h"
 #include "BLI_rand.h"
 #include "BLI_jitter.h"
 #include "BLI_math.h"
@@ -182,6 +183,13 @@ void psys_reset(ParticleSystem *psys, int mode)
 
 	/* reset point cache */
 	BKE_ptcache_invalidate(psys->pointcache);
+
+	if(psys->fluid_springs) {
+		MEM_freeN(psys->fluid_springs);
+		psys->fluid_springs = NULL;
+	}
+
+	psys->tot_fluidsprings = psys->alloc_fluidsprings = 0;
 }
 
 static void realloc_particles(ParticleSimulationData *sim, int new_totpart)
@@ -2228,32 +2236,79 @@ static void psys_update_effectors(ParticleSimulationData *sim)
  Presented at Siggraph, (2005)
 
 ***********************************************************************************************************/
-static void particle_fluidsim(ParticleSystem *psys, int own_psys, ParticleData *pa, float dtime, float mass, float *gravity)
+#define PSYS_FLUID_SPRINGS_INITIAL_SIZE 256
+ParticleSpring *add_fluid_spring(ParticleSystem *psys, ParticleSpring *spring)
+{
+	/* Are more refs required? */
+	if(psys->alloc_fluidsprings == 0 || psys->fluid_springs == NULL) {
+		psys->alloc_fluidsprings = PSYS_FLUID_SPRINGS_INITIAL_SIZE;
+		psys->fluid_springs = (ParticleSpring*)MEM_callocN(psys->alloc_fluidsprings * sizeof(ParticleSpring), "Particle Fluid Springs");
+	}
+	else if(psys->tot_fluidsprings == psys->alloc_fluidsprings) {
+		/* Double the number of refs allocated */
+		psys->alloc_fluidsprings *= 2;
+		psys->fluid_springs = (ParticleSpring*)MEM_reallocN(psys->fluid_springs, psys->alloc_fluidsprings * sizeof(ParticleSpring));
+	}
+
+	memcpy(psys->fluid_springs + psys->tot_fluidsprings, spring, sizeof(ParticleSpring));
+	psys->tot_fluidsprings++;
+
+	return psys->fluid_springs + psys->tot_fluidsprings - 1;
+}
+
+void  delete_fluid_spring(ParticleSystem *psys, int j)
+{
+	if (j != psys->tot_fluidsprings - 1)
+		psys->fluid_springs[j] = psys->fluid_springs[psys->tot_fluidsprings - 1];
+
+	psys->tot_fluidsprings--;
+
+	if (psys->tot_fluidsprings < psys->alloc_fluidsprings/2 && psys->alloc_fluidsprings > PSYS_FLUID_SPRINGS_INITIAL_SIZE){
+		psys->alloc_fluidsprings /= 2;
+		psys->fluid_springs = (ParticleSpring*)MEM_reallocN(psys->fluid_springs,  psys->alloc_fluidsprings * sizeof(ParticleSpring));
+	}
+}
+
+EdgeHash *build_fluid_springhash(ParticleSystem *psys)
+{
+	EdgeHash *springhash = NULL;
+	ParticleSpring *spring = psys->fluid_springs;
+	int i = 0;
+
+	springhash = BLI_edgehash_new();
+
+	for(i=0, spring=psys->fluid_springs; i<psys->tot_fluidsprings; i++, spring++)
+		BLI_edgehash_insert(springhash, spring->particle_index[0], spring->particle_index[1], SET_INT_IN_POINTER(i+1));
+
+	return springhash;
+}
+static void particle_fluidsim(ParticleSystem *psys, int own_psys, ParticleData *pa, float dtime, float mass, float *gravity, EdgeHash *springhash)
 {
 	SPHFluidSettings *fluid = psys->part->fluid;
 	KDTreeNearest *ptn = NULL;
 	ParticleData *npa;
+	ParticleSpring *spring = NULL;
 
 	float temp[3];
-	float q, q1, u, I, D;
+	float q, q1, u, I, D, rij, d, Lij;
 	float pressure_near, pressure;
 	float p=0, pnear=0;
 
-	float radius = fluid->radius;
 	float omega = fluid->viscosity_omega;
 	float beta = fluid->viscosity_beta;
 	float massfactor = 1.0f/mass;
 	float spring_k = fluid->spring_k;
-	float L = fluid->rest_length;
+	float h = fluid->radius;
+	float L = fluid->rest_length * fluid->radius;
 
-	int n, neighbours = BLI_kdtree_range_search(psys->tree, radius, pa->prev_state.co, NULL, &ptn);
-	int index = own_psys ? pa - psys->particles : -1;
+	int n, neighbours = BLI_kdtree_range_search(psys->tree, h, pa->prev_state.co, NULL, &ptn);
+	int spring_index = 0, index = own_psys ? pa - psys->particles : -1;
 
 	/* pressure and near pressure */
 	for(n=own_psys?1:0; n<neighbours; n++) {
 		sub_v3_v3(ptn[n].co, pa->prev_state.co);
 		mul_v3_fl(ptn[n].co, 1.f/ptn[n].dist);
-		q = ptn[n].dist/radius;
+		q = ptn[n].dist/h;
 
 		if(q < 1.f) {
 			q1 = 1.f - q;
@@ -2272,7 +2327,8 @@ static void particle_fluidsim(ParticleSystem *psys, int own_psys, ParticleData *
 	for(n=own_psys?1:0; n<neighbours; n++) {
 		npa = psys->particles + ptn[n].index;
 
-		q = ptn[n].dist/radius;
+		rij = ptn[n].dist;
+		q = rij/h;
 		q1 = 1.f-q;
 
 		/* Double Density Relaxation - Algorithm 2 (can't be thread safe!)*/
@@ -2296,14 +2352,40 @@ static void particle_fluidsim(ParticleSystem *psys, int own_psys, ParticleData *
 				}
 			}
 
-			/* Hooke's spring force */
 			if(spring_k > 0.f) {
-				/* L is a factor of radius */
-				D = 0.5 * dtime * dtime * 10.f * fluid->spring_k * (1.f - L) * (L - q);
+				/* Viscoelastic spring force - Algorithm 4*/
+				if (fluid->flag & SPH_VISCOELASTIC_SPRINGS && springhash){
+					spring_index = GET_INT_FROM_POINTER(BLI_edgehash_lookup(springhash, index, ptn[n].index));
+
+					if(spring_index) {
+						spring = psys->fluid_springs + spring_index - 1;
+					}
+					else {
+						ParticleSpring temp_spring;
+						temp_spring.particle_index[0] = index;
+						temp_spring.particle_index[1] = ptn[n].index;
+						temp_spring.rest_length = (fluid->flag & SPH_CURRENT_REST_LENGTH) ? rij : L;
+						temp_spring.delete_flag = 0;
+						
+						spring = add_fluid_spring(psys, &temp_spring);
+					}
+
+					Lij = spring->rest_length;
+					d = fluid->yield_ratio * Lij;
 
-				madd_v3_v3fl(pa->state.co, ptn[n].co, -D * massfactor);
-				if(own_psys)
-					madd_v3_v3fl(npa->state.co, ptn[n].co, D * massfactor);
+					if (rij > Lij + d) // Stretch, 25 is just a multiplier for plasticity_constant value to counter default dtime of 1/25
+						spring->rest_length += dtime * 25.f * fluid->plasticity_constant * (rij - Lij - d);
+					else if(rij < Lij - d) // Compress
+						spring->rest_length -= dtime * 25.f * fluid->plasticity_constant * (Lij - d - rij);
+				}
+				else { /* PART_SPRING_HOOKES - Hooke's spring force */
+					/* L is a factor of radius */
+					D = 0.5 * dtime * dtime * 10.f * fluid->spring_k * (1.f - L/h) * (L - rij);
+ 
+					madd_v3_v3fl(pa->state.co, ptn[n].co, -D * massfactor);
+					if(own_psys)
+						madd_v3_v3fl(npa->state.co, ptn[n].co, D * massfactor);
+				}
 			}
 		}
 	} 
@@ -2318,21 +2400,63 @@ static void particle_fluidsim(ParticleSystem *psys, int own_psys, ParticleData *
 		MEM_freeN(ptn);
 }
 
-static void apply_particle_fluidsim(Object *ob, ParticleSystem *psys, ParticleData *pa, float dtime, float *gravity){
+static void apply_particle_fluidsim(Object *ob, ParticleSystem *psys, ParticleData *pa, float dtime, float *gravity, EdgeHash *springhash){
 	ParticleTarget *pt;
 
-	particle_fluidsim(psys, 1, pa, dtime, psys->part->mass, gravity);
+	particle_fluidsim(psys, 1, pa, dtime, psys->part->mass, gravity, springhash);
 	
 	/*----check other SPH systems (Multifluids) , each fluid has its own parameters---*/
 	for(pt=psys->targets.first; pt; pt=pt->next) {
 		ParticleSystem *epsys = psys_get_target_system(ob, pt);
 
 		if(epsys)
-			particle_fluidsim(epsys, 0, pa, dtime, psys->part->mass, gravity);
+			particle_fluidsim(epsys, 0, pa, dtime, psys->part->mass, gravity, NULL);
 	}
 	/*----------------------------------------------------------------*/	 	 
 }
 
+static void apply_fluid_springs(ParticleSystem *psys, ParticleSettings *part, float timestep){
+	SPHFluidSettings *fluid = psys->part->fluid;
+	ParticleData *pa1, *pa2;
+	ParticleSpring *spring = psys->fluid_springs;
+	
+	float h = fluid->radius;
+	float massfactor = 1.0f/psys->part->mass;
+	float D, Rij[3], rij, Lij;
+	int i;
+
+	if((fluid->flag & SPH_VISCOELASTIC_SPRINGS)==0 || fluid->spring_k == 0.f)
+		return;
+
+	/* Loop through the springs */
+	for(i=0; i<psys->tot_fluidsprings; i++, spring++) {
+		Lij = spring->rest_length;
+
+		if (Lij > h) {
+			spring->delete_flag = 1;
+		}
+		else {
+			pa1 = psys->particles + spring->particle_index[0];
+			pa2 = psys->particles + spring->particle_index[1];
+
+			sub_v3_v3v3(Rij, pa2->prev_state.co, pa1->prev_state.co);
+			rij = normalize_v3(Rij);
+
+			/* Calculate displacement and apply value */
+			D =  0.5f * timestep * timestep * 10.f * fluid->spring_k * (1.f - Lij/h) * (Lij - rij);
+
+			madd_v3_v3fl(pa1->state.co, Rij, -D * pa1->state.time * pa1->state.time * massfactor);
+			madd_v3_v3fl(pa2->state.co, Rij, D * pa2->state.time * pa2->state.time * massfactor);
+		}
+	}
+
+	/* Loop through springs backwaqrds - for efficient delete function */
+	for (i=psys->tot_fluidsprings-1; i >= 0; i--) {
+		if(psys->fluid_springs[i].delete_flag)
+			delete_fluid_spring(psys, i);
+	}
+}
+
 /************************************************/
 /*			Newtonian physics					*/
 /************************************************/
@@ -3420,6 +3544,7 @@ static void dynamics_step(ParticleSimulationData *sim, float cfra)
 		}
 		case PART_PHYS_FLUID:
 		{
+			EdgeHash *springhash = build_fluid_springhash(psys);
 			float *gravity = NULL;
 
 			if(psys_uses_gravity(sim))
@@ -3434,9 +3559,12 @@ static void dynamics_step(ParticleSimulationData *sim, float cfra)
 
 			/* actual fluids calculations (not threadsafe!) */
 			LOOP_DYNAMIC_PARTICLES {
-				apply_particle_fluidsim(sim->ob, psys, pa, pa->state.time*timestep, gravity);
+				apply_particle_fluidsim(sim->ob, psys, pa, pa->state.time*timestep, gravity, springhash);
 			}
 
+			/* Apply springs to particles */
+			apply_fluid_springs(psys, part, timestep);
+
 			/* apply velocity, collisions and rotation */
 			LOOP_DYNAMIC_PARTICLES {
 				/* velocity holds forces and viscosity, so apply them before collisions */
@@ -3452,6 +3580,11 @@ static void dynamics_step(ParticleSimulationData *sim, float cfra)
 				/* SPH particles are not physical particles, just interpolation particles,  thus rotation has not a direct sense for them */	
 				rotate_particle(part, pa, pa->state.time, timestep);  
 			}
+
+			if(springhash) {
+				BLI_edgehash_free(springhash, NULL);
+				springhash = NULL;
+			}
 			break;
 		}
 	}
@@ -3696,6 +3829,13 @@ static void system_step(ParticleSimulationData *sim, float cfra)
 		/* reset only just created particles (on startframe all particles are recreated) */
 		reset_all_particles(sim, 0.0, cfra, oldtotpart);
 
+		if (psys->fluid_springs) {
+			MEM_freeN(psys->fluid_springs);
+			psys->fluid_springs = NULL;
+		}
+
+		psys->tot_fluidsprings = psys->alloc_fluidsprings = 0;
+
 		/* flag for possible explode modifiers after this system */
 		sim->psmd->flag |= eParticleSystemFlag_Pars;
 
@@ -3851,6 +3991,8 @@ static void fluid_default_settings(ParticleSettings *part){
 
 	fluid->radius = 0.5f;
 	fluid->spring_k = 0.f;
+	fluid->plasticity_constant = 0.1f;
+	fluid->yield_ratio = 0.1f;
 	fluid->rest_length = 0.5f;
 	fluid->viscosity_omega = 2.f;
 	fluid->viscosity_beta = 0.f;
diff --git a/source/blender/blenkernel/intern/pointcache.c b/source/blender/blenkernel/intern/pointcache.c
index eb0601b413e..5408e57f10d 100644
--- a/source/blender/blenkernel/intern/pointcache.c
+++ b/source/blender/blenkernel/intern/pointcache.c
@@ -390,6 +390,48 @@ static int  ptcache_particle_totwrite(void *psys_v, int cfra)
 	return totwrite;
 }
 
+static void ptcache_particle_extra_write(void *psys_v, PTCacheMem *pm, int UNUSED(cfra))
+{
+	ParticleSystem *psys = psys_v;
+	PTCacheExtra *extra = NULL;
+
+	if(psys->part->phystype == PART_PHYS_FLUID &&
+		psys->part->fluid && psys->part->fluid->flag & SPH_VISCOELASTIC_SPRINGS &&
+		psys->tot_fluidsprings && psys->fluid_springs) {
+
+		extra = MEM_callocN(sizeof(PTCacheExtra), "Point cache: fluid extra data");
+
+		extra->type = BPHYS_EXTRA_FLUID_SPRINGS;
+		extra->totdata = psys->tot_fluidsprings;
+
+		extra->data = MEM_callocN(extra->totdata * ptcache_extra_datasize[extra->type], "Point cache: extra data");
+		memcpy(extra->data, psys->fluid_springs, extra->totdata * ptcache_extra_datasize[extra->type]);
+
+		BLI_addtail(&pm->extradata, extra);
+	}
+}
+
+static int ptcache_particle_extra_read(void *psys_v, PTCacheMem *pm, float UNUSED(cfra))
+{
+	ParticleSystem *psys = psys_v;
+	PTCacheExtra *extra = pm->extradata.first;
+
+	for(; extra; extra=extra->next) {
+		switch(extra->type) {
+			case BPHYS_EXTRA_FLUID_SPRINGS:
+			{
+				if(psys->fluid_springs)
+					MEM_freeN(psys->fluid_springs);
+
+				psys->fluid_springs = MEM_dupallocN(extra->data);
+				psys->tot_fluidsprings = psys->alloc_fluidsprings = extra->totdata;
+				break;
+			}
+		}
+	}
+	return 1;
+}
+
 /* Cloth functions */
 static int  ptcache_cloth_write(int index, void *cloth_v, void **data, int UNUSED(cfra))
 {
@@ -667,6 +709,10 @@ void BKE_ptcache_id_from_particles(PTCacheID *pid, Object *ob, ParticleSystem *p
 
 	if(psys->part->phystype == PART_PHYS_BOIDS)
 		pid->data_types|= (1<<BPHYS_DATA_AVELOCITY) | (1<<BPHYS_DATA_ROTATION) | (1<<BPHYS_DATA_BOIDS);
+	else if(psys->part->phystype == PART_PHYS_FLUID && psys->part->fluid && psys->part->fluid->flag & SPH_VISCOELASTIC_SPRINGS) {
+		pid->write_extra_data = ptcache_particle_extra_write;
+		pid->read_extra_data = ptcache_particle_extra_read;
+	}
 
 	if(psys->part->rotmode!=PART_ROT_VEL
 		|| psys->part->avemode!=PART_AVE_SPIN || psys->part->avefac!=0.0f)
@@ -1261,9 +1307,13 @@ static void ptcache_extra_free(PTCacheMem *pm)
 {
 	PTCacheExtra *extra = pm->extradata.first;
 
-	for(; extra; extra=extra->next) {
-		if(extra->data)
-			MEM_freeN(extra->data);
+	if(extra) {
+		for(; extra; extra=extra->next) {
+			if(extra->data)
+				MEM_freeN(extra->data);
+		}
+
+		BLI_freelistN(&pm->extradata);
 	}
 }
 static int ptcache_old_elemsize(PTCacheID *pid)
@@ -1383,16 +1433,14 @@ static PTCacheMem *ptcache_disk_frame_to_mem(PTCacheID *pid, int cfra)
 
 			extra->type = extratype;
 
-			ptcache_file_read(pf, &extra->flag, 1, sizeof(unsigned int));
 			ptcache_file_read(pf, &extra->totdata, 1, sizeof(unsigned int));
-			ptcache_file_read(pf, &extra->datasize, 1, sizeof(unsigned int));
 
-			extra->data = MEM_callocN(extra->totdata * extra->datasize, "Pointcache extradata->data");
+			extra->data = MEM_callocN(extra->totdata * ptcache_extra_datasize[extra->type], "Pointcache extradata->data");
 
 			if(pf->flag & PTCACHE_TYPEFLAG_COMPRESS)
-				ptcache_file_compressed_read(pf, (unsigned char*)(extra->data), extra->totdata*extra->datasize);
+				ptcache_file_compressed_read(pf, (unsigned char*)(extra->data), extra->totdata*ptcache_extra_datasize[extra->type]);
 			else
-				ptcache_file_read(pf, extra->data, extra->totdata, extra->datasize);
+				ptcache_file_read(pf, extra->data, extra->totdata, ptcache_extra_datasize[extra->type]);
 
 			BLI_addtail(&pm->extradata, extra);
 		}
@@ -1475,18 +1523,16 @@ static int ptcache_mem_frame_to_disk(PTCacheID *pid, PTCacheMem *pm)
 				continue;
 
 			ptcache_file_write(pf, &extra->type, 1, sizeof(unsigned int));
-			ptcache_file_write(pf, &extra->flag, 1, sizeof(unsigned int));
 			ptcache_file_write(pf, &extra->totdata, 1, sizeof(unsigned int));
-			ptcache_file_write(pf, &extra->datasize, 1, sizeof(unsigned int));
 
 			if(pid->cache->compression) {
-				unsigned int in_len = extra->totdata * extra->datasize;
+				unsigned int in_len = extra->totdata * ptcache_extra_datasize[extra->type];
 				unsigned char *out = (unsigned char *)MEM_callocN(LZO_OUT_LEN(in_len)*4, "pointcache_lzo_buffer");
 				ptcache_file_compressed_write(pf, (unsigned char*)(extra->data), in_len, out, pid->cache->compression);
 				MEM_freeN(out);
 			}
 			else {
-				ptcache_file_write(pf, extra->data, extra->totdata, extra->datasize);
+				ptcache_file_write(pf, extra->data, extra->totdata, ptcache_extra_datasize[extra->type]);
 			}
 		}
 	}