Partial response force for hair collisions.

This implements a penalty force as well as a repulsion force to avoid
further penetration, as suggested in
"Simulating Complex Hair with Robust Collision Handling"
(http://graphics.snu.ac.kr/publications/2005-choe-HairSim/Choe_2005_SCA.pdf)

Friction forces are still missing. More problematic is handling of
moving colliders, when face swap places with the hair vertex and a
collision is missed, putting the vertex inside the mesh volume. Larger
margins might help, but ultimately using Bullet collision detection is
probably more reliable and failsafe.

6 files changed, 169 insertions, 57 deletions

diff --git a/source/blender/blenkernel/BKE_effect.h b/source/blender/blenkernel/BKE_effect.h
index d6991a473b0..852f9de4c09 100644
--- a/source/blender/blenkernel/BKE_effect.h
+++ b/source/blender/blenkernel/BKE_effect.h
@@ -160,6 +160,7 @@ struct SimDebugData *BKE_sim_debug_data_new(void);
 void BKE_sim_debug_data_add_dot(struct SimDebugData *debug_data, const float p[3], float r, float g, float b, int hash);
 void BKE_sim_debug_data_add_line(struct SimDebugData *debug_data, const float p1[3], const float p2[3], float r, float g, float b, int hash);
 void BKE_sim_debug_data_add_vector(struct SimDebugData *debug_data, const float p[3], const float d[3], float r, float g, float b, int hash);
+void BKE_sim_debug_data_remove(struct SimDebugData *debug_data, int hash);
 void BKE_sim_debug_data_clear(struct SimDebugData *debug_data);
 void BKE_sim_debug_data_free(struct SimDebugData *debug_data);
 
diff --git a/source/blender/blenkernel/intern/collision.c b/source/blender/blenkernel/intern/collision.c
index b38609e3a31..94e2c55b804 100644
--- a/source/blender/blenkernel/intern/collision.c
+++ b/source/blender/blenkernel/intern/collision.c
@@ -33,6 +33,7 @@
 #include "MEM_guardedalloc.h"
 
 #include "DNA_cloth_types.h"
+#include "DNA_effect_types.h"
 #include "DNA_group_types.h"
 #include "DNA_object_types.h"
 #include "DNA_object_force.h"
@@ -45,6 +46,7 @@
 #include "BLI_edgehash.h"
 
 #include "BKE_cloth.h"
+#include "BKE_effect.h"
 #include "BKE_modifier.h"
 #include "BKE_scene.h"
 
@@ -59,6 +61,41 @@
 #endif
 
 
+/* ==== hash functions for debugging ==== */
+static unsigned int hash_int_2d(unsigned int kx, unsigned int ky)
+{
+#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
+
+	unsigned int a, b, c;
+
+	a = b = c = 0xdeadbeef + (2 << 2) + 13;
+	a += kx;
+	b += ky;
+
+	c ^= b; c -= rot(b,14);
+	a ^= c; a -= rot(c,11);
+	b ^= a; b -= rot(a,25);
+	c ^= b; c -= rot(b,16);
+	a ^= c; a -= rot(c,4);
+	b ^= a; b -= rot(a,14);
+	c ^= b; c -= rot(b,24);
+
+	return c;
+
+#undef rot
+}
+
+static int hash_vertex(int type, int vertex)
+{
+	return hash_int_2d((unsigned int)type, (unsigned int)vertex);
+}
+
+static int hash_collpair(int type, CollPair *collpair)
+{
+	return hash_int_2d((unsigned int)type, hash_int_2d((unsigned int)collpair->face1, (unsigned int)collpair->face2));
+}
+/* ================ */
+
 /***********************************
 Collision modifier code start
 ***********************************/
@@ -914,24 +951,35 @@ int cloth_bvh_objcollision(Object *ob, ClothModifierData *clmd, float step, floa
 	return 1|MIN2 ( ret, 1 );
 }
 
+BLI_INLINE void max_v3_v3v3(float r[3], const float a[3], const float b[3])
+{
+	r[0] = max_ff(a[0], b[0]);
+	r[1] = max_ff(a[1], b[1]);
+	r[2] = max_ff(a[2], b[2]);
+}
 
-static int cloth_points_collision_response_static(ClothModifierData *clmd, CollisionModifierData *collmd, CollPair *collpair, CollPair *collision_end)
+static bool cloth_points_collision_response_static(ClothModifierData *clmd, CollisionModifierData *collmd, PartDeflect *pd,
+                                                  CollPair *collpair, CollPair *collision_end, float dt)
 {
-	int result = 0;
-	Cloth *cloth1;
+	bool result = false;
+	float restitution = (1.0f - clmd->coll_parms->damping) * (1.0f - pd->pdef_sbdamp);
+	float inv_dt = 1.0f / dt;
+	Cloth *cloth1 = clmd->clothObject;
+	
 	float w1, w2, u1, u2, u3;
-	float v1[3], v2[3], relativeVelocity[3];
-	float magrelVel;
+	float v1[3], v2_old[3], v2_new[3], v_rel_old[3], v_rel_new[3];
+//	float magrelVel;
 	float epsilon2 = BLI_bvhtree_getepsilon ( collmd->bvhtree );
 
-	cloth1 = clmd->clothObject;
-
 	for ( ; collpair != collision_end; collpair++ ) {
-//		float i1[3], i2[3], i3[3];
+		float margin_distance = collpair->distance - epsilon2;
+		float impulse[3];
+		float mag_v_rel;
 
-//		zero_v3(i1);
-//		zero_v3(i2);
-//		zero_v3(i3);
+		if (margin_distance > 0.0f)
+			continue;
+
+		zero_v3(impulse);
 
 		/* only handle static collisions here */
 		if ( collpair->flag & COLLISION_IN_FUTURE )
@@ -951,17 +999,75 @@ static int cloth_points_collision_response_static(ClothModifierData *clmd, Colli
 		/* Calculate relative velocity */
 		copy_v3_v3(v1, cloth1->verts[collpair->ap1].tv);
 
-		collision_interpolateOnTriangle ( v2, collmd->current_v[collpair->bp1].co, collmd->current_v[collpair->bp2].co, collmd->current_v[collpair->bp3].co, u1, u2, u3 );
+		collision_interpolateOnTriangle ( v2_new, collmd->current_v[collpair->bp1].co, collmd->current_v[collpair->bp2].co, collmd->current_v[collpair->bp3].co, u1, u2, u3 );
+		/* XXX assume constant velocity of the collider for now */
+		copy_v3_v3(v2_old, v2_new);
 
-		sub_v3_v3v3(relativeVelocity, v2, v1);
+		sub_v3_v3v3(v_rel_old, v1, v2_old);
+		sub_v3_v3v3(v_rel_new, v1, v2_new);
 
-		/* Calculate the normal component of the relative velocity (actually only the magnitude - the direction is stored in 'normal'). */
-		magrelVel = dot_v3v3(relativeVelocity, collpair->normal);
+		/* normal component of the relative velocity */
+		mag_v_rel = dot_v3v3(v_rel_old, collpair->normal);
 
-		/* printf("magrelVel: %f\n", magrelVel); */
+		/**** DEBUG ****/
+		if (clmd->debug_data) {
+			BKE_sim_debug_data_add_dot(clmd->debug_data, collpair->pa, 0.9, 0.2, 0.2, hash_collpair(833, collpair));
+			BKE_sim_debug_data_add_dot(clmd->debug_data, collpair->pb, 0.2, 0.9, 0.2, hash_collpair(834, collpair));
+			BKE_sim_debug_data_add_line(clmd->debug_data, collpair->pa, collpair->pb, 0.8, 0.8, 0.8, hash_collpair(835, collpair));
+			BKE_sim_debug_data_add_vector(clmd->debug_data, collpair->pa, collpair->normal, 1.0, 1.0, 0.0, hash_collpair(836, collpair));
+		}
+		/********/
 
-		/* Calculate masses of points.
-		 * TODO */
+		if (mag_v_rel < -ALMOST_ZERO) {
+			float v_nor_old, v_nor_new;
+			float v_tan_old[3], v_tan_new[3];
+			float repulse[3];
+			
+			/* Collision response based on
+			 * "Simulating Complex Hair with Robust Collision Handling" (Choe, Choi, Ko, ACM SIGGRAPH 2005)
+			 * http://graphics.snu.ac.kr/publications/2005-choe-HairSim/Choe_2005_SCA.pdf
+			 */
+			
+			v_nor_old = mag_v_rel;
+			v_nor_new = dot_v3v3(v_rel_new, collpair->normal);
+			
+			madd_v3_v3v3fl(v_tan_old, v_rel_old, collpair->normal, -v_nor_old);
+			madd_v3_v3v3fl(v_tan_new, v_rel_new, collpair->normal, -v_nor_new);
+			
+			mul_v3_v3fl(repulse, collpair->normal, -margin_distance * inv_dt);
+			sub_v3_v3(repulse, v1);
+			
+//			if (margin_distance < -epsilon2) {
+			{
+				float bounce[3];
+				
+				mul_v3_v3fl(bounce, collpair->normal, -(v_nor_new + v_nor_old * restitution));
+//				max_v3_v3v3(impulse, repulse, bounce);
+				copy_v3_v3(impulse, bounce);
+			}
+//			else {
+//				copy_v3_v3(impulse, repulse);
+//			}
+			cloth1->verts[collpair->ap1].impulse_count++;
+			BKE_sim_debug_data_add_vector(clmd->debug_data, collpair->pa, impulse, 0.0, 1.0, 0.6, hash_collpair(873, collpair));
+			
+			result = true;
+		}
+		else {
+			BKE_sim_debug_data_remove(clmd->debug_data, hash_collpair(833, collpair));
+			BKE_sim_debug_data_remove(clmd->debug_data, hash_collpair(834, collpair));
+			BKE_sim_debug_data_remove(clmd->debug_data, hash_collpair(835, collpair));
+			BKE_sim_debug_data_remove(clmd->debug_data, hash_collpair(873, collpair));
+		}
+		
+		if (result) {
+			int i = 0;
+
+			for (i = 0; i < 3; i++) {
+				if (cloth1->verts[collpair->ap1].impulse_count > 0 && fabsf(cloth1->verts[collpair->ap1].impulse[i]) < fabsf(impulse[i]))
+					cloth1->verts[collpair->ap1].impulse[i] = impulse[i];
+			}
+		}
 
 #if 0
 		/* If v_n_mag < 0 the edges are approaching each other. */
@@ -1163,7 +1269,8 @@ static void cloth_points_objcollisions_nearcheck(ClothModifierData * clmd, Colli
 	}
 }
 
-static int cloth_points_objcollisions_resolve ( ClothModifierData * clmd, CollisionModifierData *collmd, CollPair *collisions, CollPair *collisions_index)
+static int cloth_points_objcollisions_resolve(ClothModifierData * clmd, CollisionModifierData *collmd, PartDeflect *pd,
+                                              CollPair *collisions, CollPair *collisions_index, float dt)
 {
 	Cloth *cloth = clmd->clothObject;
 	int i=0, numverts = clmd->clothObject->numverts;
@@ -1172,7 +1279,7 @@ static int cloth_points_objcollisions_resolve ( ClothModifierData * clmd, Collis
 	
 	// process all collisions
 	if ( collmd->bvhtree ) {
-		int result = cloth_points_collision_response_static(clmd, collmd, collisions, collisions_index);
+		bool result = cloth_points_collision_response_static(clmd, collmd, pd, collisions, collisions_index, dt);
 		
 		// apply impulses in parallel
 		if (result) {
@@ -1189,36 +1296,6 @@ static int cloth_points_objcollisions_resolve ( ClothModifierData * clmd, Collis
 			}
 		}
 	}
-#if 0
-	// process all collisions (calculate impulses, TODO: also repulses if distance too short)
-	result = 1;
-	for ( j = 0; j < 2; j++ ) { /* 5 is just a value that ensures convergence */
-		result = 0;
-
-		if ( collmd->bvhtree ) {
-			result += cloth_points_collision_response_static(clmd, collmd, collisions, collisions_index);
-
-			// apply impulses in parallel
-			if (result) {
-				for (i = 0; i < numverts; i++) {
-					// calculate "velocities" (just xnew = xold + v; no dt in v)
-					if (verts[i].impulse_count) {
-						// VECADDMUL ( verts[i].tv, verts[i].impulse, 1.0f / verts[i].impulse_count );
-						VECADD ( verts[i].tv, verts[i].tv, verts[i].impulse);
-						zero_v3(verts[i].impulse);
-						verts[i].impulse_count = 0;
-
-						ret++;
-					}
-				}
-			}
-		}
-
-		if (!result) {
-			break;
-		}
-	}
-#endif
 	
 	return ret;
 }
@@ -1244,7 +1321,7 @@ int cloth_points_objcollision(Object *ob, ClothModifierData *clmd, float step, f
 	////////////////////////////////////////////////////////////
 	
 	// create temporary cloth points bvh
-	cloth_bvh = BLI_bvhtree_new(numverts, MAX2(clmd->coll_parms->epsilon, clmd->coll_parms->distance_repel), 2, 26);
+	cloth_bvh = BLI_bvhtree_new(numverts, MAX2(clmd->coll_parms->epsilon, clmd->coll_parms->distance_repel), 4, 6);
 	/* fill tree */
 	for (i = 0; i < numverts; i++) {
 		float co[6];
@@ -1300,7 +1377,7 @@ int cloth_points_objcollision(Object *ob, ClothModifierData *clmd, float step, f
 				                                     result, overlap, round_dt);
 				
 				// resolve nearby collisions
-				ret += cloth_points_objcollisions_resolve(clmd, collmd, collisions[i], collisions_index[i]);
+				ret += cloth_points_objcollisions_resolve(clmd, collmd, collob->pd, collisions[i], collisions_index[i], round_dt);
 				ret2 += ret;
 			}
 			
diff --git a/source/blender/blenkernel/intern/effect.c b/source/blender/blenkernel/intern/effect.c
index 94b4af10201..0cbd7376e4f 100644
--- a/source/blender/blenkernel/intern/effect.c
+++ b/source/blender/blenkernel/intern/effect.c
@@ -1072,7 +1072,11 @@ static void debug_data_insert(SimDebugData *debug_data, SimDebugElement *elem)
 
 void BKE_sim_debug_data_add_dot(struct SimDebugData *debug_data, const float p[3], float r, float g, float b, int hash)
 {
-	SimDebugElement *elem = MEM_callocN(sizeof(SimDebugElement), "sim debug data element");
+	SimDebugElement *elem;
+	if (!debug_data)
+		return;
+	
+	elem = MEM_callocN(sizeof(SimDebugElement), "sim debug data element");
 	elem->type = SIM_DEBUG_ELEM_DOT;
 	elem->hash = hash;
 	elem->color[0] = r;
@@ -1085,7 +1089,11 @@ void BKE_sim_debug_data_add_dot(struct SimDebugData *debug_data, const float p[3
 
 void BKE_sim_debug_data_add_line(struct SimDebugData *debug_data, const float p1[3], const float p2[3], float r, float g, float b, int hash)
 {
-	SimDebugElement *elem = MEM_callocN(sizeof(SimDebugElement), "sim debug data element");
+	SimDebugElement *elem;
+	if (!debug_data)
+		return;
+	
+	elem = MEM_callocN(sizeof(SimDebugElement), "sim debug data element");
 	elem->type = SIM_DEBUG_ELEM_LINE;
 	elem->hash = hash;
 	elem->color[0] = r;
@@ -1099,7 +1107,11 @@ void BKE_sim_debug_data_add_line(struct SimDebugData *debug_data, const float p1
 
 void BKE_sim_debug_data_add_vector(struct SimDebugData *debug_data, const float p[3], const float d[3], float r, float g, float b, int hash)
 {
-	SimDebugElement *elem = MEM_callocN(sizeof(SimDebugElement), "sim debug data element");
+	SimDebugElement *elem;
+	if (!debug_data)
+		return;
+	
+	elem = MEM_callocN(sizeof(SimDebugElement), "sim debug data element");
 	elem->type = SIM_DEBUG_ELEM_VECTOR;
 	elem->hash = hash;
 	elem->color[0] = r;
@@ -1111,6 +1123,16 @@ void BKE_sim_debug_data_add_vector(struct SimDebugData *debug_data, const float
 	debug_data_insert(debug_data, elem);
 }
 
+void BKE_sim_debug_data_remove(SimDebugData *debug_data, int hash)
+{
+	SimDebugElement dummy;
+	if (!debug_data)
+		return;
+	
+	dummy.hash = hash;
+	BLI_ghash_remove(debug_data->gh, &dummy, NULL, debug_element_free);
+}
+
 void BKE_sim_debug_data_clear(SimDebugData *debug_data)
 {
 	if (!debug_data)
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index 054c9cb96e7..1a772a9657e 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -113,6 +113,7 @@
 
 #include "BKE_armature.h"
 #include "BKE_brush.h"
+#include "BKE_cloth.h"
 #include "BKE_constraint.h"
 #include "BKE_context.h"
 #include "BKE_curve.h"
@@ -3940,6 +3941,9 @@ static void direct_link_particlesystems(FileData *fd, ListBase *particles)
 				if (psys->clmd->sim_parms->presets > 10)
 					psys->clmd->sim_parms->presets = 0;
 			}
+			if (psys->clmd->coll_parms) {
+				psys->clmd->coll_parms->flags |= CLOTH_COLLSETTINGS_FLAG_POINTS;
+			}
 			
 			psys->hair_in_dm = psys->hair_out_dm = NULL;
 			
diff --git a/source/blender/makesdna/DNA_cloth_types.h b/source/blender/makesdna/DNA_cloth_types.h
index a9e066ef45e..4d862e48109 100644
--- a/source/blender/makesdna/DNA_cloth_types.h
+++ b/source/blender/makesdna/DNA_cloth_types.h
@@ -99,15 +99,16 @@ typedef struct ClothCollSettings {
 	float	epsilon;		/* min distance for collisions.		*/
 	float	self_friction;		/* Fiction/damping with self contact. */
 	float	friction;		/* Friction/damping applied on contact with other object.*/
+	float	damping;	/* Collision restitution on contact with other object.*/
 	float 	selfepsilon; 		/* for selfcollision */
 	float repel_force, distance_repel;
 	int	flags;			/* collision flags defined in BKE_cloth.h */
 	short	self_loop_count;	/* How many iterations for the selfcollision loop	*/
 	short	loop_count;		/* How many iterations for the collision loop.		*/
+	int pad;
 	struct Group *group;	/* Only use colliders from this group of objects */
 	short	vgroup_selfcol; /* vgroup to paint which vertices are used for self collisions */
-	short pad;
-	int pad2;
+	short pad2[3];
 } ClothCollSettings;
 
 
diff --git a/source/blender/makesrna/intern/rna_cloth.c b/source/blender/makesrna/intern/rna_cloth.c
index 9ab6791b5fa..4b2d2dac25d 100644
--- a/source/blender/makesrna/intern/rna_cloth.c
+++ b/source/blender/makesrna/intern/rna_cloth.c
@@ -589,6 +589,13 @@ static void rna_def_cloth_collision_settings(BlenderRNA *brna)
 	RNA_def_property_ui_text(prop, "Friction", "Friction force if a collision happened (higher = less movement)");
 	RNA_def_property_update(prop, 0, "rna_cloth_update");
 
+	prop = RNA_def_property(srna, "damping", PROP_FLOAT, PROP_FACTOR);
+	RNA_def_property_float_sdna(prop, NULL, "damping");
+	RNA_def_property_range(prop, 0.0f, 1.0f);
+	RNA_def_property_float_default(prop, 1.0f);
+	RNA_def_property_ui_text(prop, "Restitution", "Amount of velocity lost on collision");
+	RNA_def_property_update(prop, 0, "rna_cloth_update");
+
 	prop = RNA_def_property(srna, "collision_quality", PROP_INT, PROP_NONE);
 	RNA_def_property_int_sdna(prop, NULL, "loop_count");
 	RNA_def_property_range(prop, 1, 20);