[Bf-blender-cvs] [4e42d01c65] cloth-improvements: Implement directional cluster based impulse pruning

Luca Rood noreply at git.blender.org
Wed Feb 1 07:11:49 CET 2017


Commit: 4e42d01c65ebda99c6531f4b32421f6032318cd9
Author: Luca Rood
Date:   Tue Jan 31 01:39:52 2017 -0200
Branches: cloth-improvements
https://developer.blender.org/rB4e42d01c65ebda99c6531f4b32421f6032318cd9

Implement directional cluster based impulse pruning

===================================================================

M	source/blender/blenkernel/intern/collision.c

===================================================================

diff --git a/source/blender/blenkernel/intern/collision.c b/source/blender/blenkernel/intern/collision.c
index 26bf0930c4..3612cb8b11 100644
--- a/source/blender/blenkernel/intern/collision.c
+++ b/source/blender/blenkernel/intern/collision.c
@@ -59,6 +59,12 @@
 #include "eltopo-capi.h"
 #endif
 
+typedef struct ImpulseCluster {
+	struct ImpulseCluster *next;
+	float dir[3];
+	float totmag;
+	float dominant_mag;
+} ImpulseCluster;
 
 /***********************************
 Collision modifier code start
@@ -171,6 +177,149 @@ void bvhtree_update_from_mvert(
 Collision modifier code end
 ***********************************/
 
+static void free_impulse_clusters(ImpulseCluster *clusters)
+{
+	while (clusters) {
+		ImpulseCluster *next = clusters->next;
+
+		MEM_freeN(clusters);
+
+		clusters = next;
+	}
+}
+
+/* This allows inserting impulses one by one into the cluster array, and immediately computing the clustering,
+ * but might cause incorrect clustering because of not knowing all impulses beforehand.
+ * TODO: Evaluate if this is good enough, as it is far cheaper than the actual hclust below. */
+#if 0
+static void insert_impulse_in_cluster_array(ImpulseCluster **clusters, const float impulse[3], const float clustang)
+{
+	ImpulseCluster **imp;
+	ImpulseCluster **close;
+	float dir[3];
+	float mag;
+	float minang = FLT_MAX;
+	float ang;
+
+	mag = normalize_v3_v3(dir, impulse);
+
+	if (mag < FLT_EPSILON) {
+		return;
+	}
+
+	for (imp = clusters; *imp; imp = &(*imp)->next) {
+		ang = angle_normalized_v3v3((*imp)->dir, dir);
+
+		if (ang < minang) {
+			minang = ang;
+			close = imp;
+		}
+	}
+
+	if (minang < clustang) {
+		/* Set total magnitude */
+		(*close)->totmag += mag;
+
+		/* Set dominant magnitude */
+		(*close)->dominant_mag = max_ff((*close)->dominant_mag, mag);
+
+		/* Interpolate direction */
+		interp_v3_v3v3_slerp((*close)->dir, (*close)->dir, dir, mag / (*close)->totmag);
+	}
+	else {
+		ImpulseCluster *tmp = MEM_mallocN(sizeof(*tmp), "cloth_collision_impulse_cluster");
+
+		tmp->next = *clusters;
+		copy_v3_v3(tmp->dir, dir);
+		tmp->totmag = mag;
+		tmp->dominant_mag = mag;
+
+		*clusters = tmp;
+	}
+}
+#endif
+
+static void insert_impulse_in_cluster_array(ImpulseCluster **clusters, const float impulse[3])
+{
+	ImpulseCluster *tmp;
+	float dir[3];
+	float mag;
+
+	mag = normalize_v3_v3(dir, impulse);
+
+	if (mag < FLT_EPSILON) {
+		return;
+	}
+
+	tmp = MEM_mallocN(sizeof(*tmp), "cloth_collision_impulse_cluster");
+
+	copy_v3_v3(tmp->dir, dir);
+	tmp->totmag = mag;
+	tmp->dominant_mag = mag;
+
+	tmp->next = *clusters;
+	*clusters = tmp;
+}
+
+BLI_INLINE bool join_closest_impulse_clusters(ImpulseCluster **clusters, const float clustang)
+{
+	ImpulseCluster **imp1, **imp2;
+	ImpulseCluster **close1, **close2;
+	float minang = FLT_MAX;
+	float ang;
+
+	for (imp1 = clusters; *imp1; imp1 = &(*imp1)->next) {
+		for (imp2 = &(*imp1)->next; *imp2; imp2 = &(*imp2)->next) {
+			ang = angle_normalized_v3v3((*imp1)->dir, (*imp2)->dir);
+
+			if (ang < minang) {
+				minang = ang;
+				close1 = imp1;
+				close2 = imp2;
+			}
+		}
+	}
+
+	if (minang < clustang) {
+		ImpulseCluster *tmp;
+
+		/* Set total magnitude */
+		(*close1)->totmag += (*close2)->totmag;
+
+		/* Set dominant magnitude */
+		(*close1)->dominant_mag = max_ff((*close1)->dominant_mag, (*close2)->dominant_mag);
+
+		/* Interpolate direction */
+		interp_v3_v3v3_slerp((*close1)->dir, (*close1)->dir, (*close2)->dir, (*close2)->totmag / (*close1)->totmag);
+
+		/* Remove merged cluster */
+		tmp = (*close2)->next;
+		MEM_freeN(*close2);
+		*close2 = tmp;
+
+		return true;
+	}
+	else {
+		return false;
+	}
+}
+
+static void compute_dominant_impulses(ImpulseCluster **clusters, float impulse[3], const float clustang)
+{
+	ImpulseCluster *tmp;
+	bool merge = true;
+
+	while (merge) {
+		merge = join_closest_impulse_clusters(clusters, clustang);
+	}
+
+	zero_v3(impulse);
+
+	for (tmp = *clusters; tmp; tmp = tmp->next) {
+		madd_v3_v3fl(impulse, tmp->dir, tmp->dominant_mag);
+	}
+}
+
 // w3 is not perfect
 static void collision_compute_barycentric ( float pv[3], float p1[3], float p2[3], float p3[3], float *w1, float *w2, float *w3 )
 {
@@ -226,7 +375,7 @@ DO_INLINE void collision_interpolateOnTriangle ( float to[3], float v1[3], float
 }
 
 static int cloth_collision_response_static (ClothModifierData *clmd, CollisionModifierData *collmd, Object *collob,
-                                            CollPair *collpair, CollPair *collision_end)
+                                            CollPair *collpair, CollPair *collision_end, ImpulseCluster **vert_imp_clusters)
 {
 	int result = 0;
 	Cloth *cloth1;
@@ -441,21 +590,16 @@ static int cloth_collision_response_static (ClothModifierData *clmd, CollisionMo
 		}
 
 		if (result) {
-			int i = 0;
-
-			/* This is a terrible approach to eliminating duplicate collision impulses, and fails as soon as impulses are not
-			 * axis aligned, or have opposite directions. Instead of this, the impulses should be clustered by direction,
-			 * and the dominant impulse magnitude from each cluster should contribute to the total impulse, in the direction
-			 * if the weighted average of the cluster's directions by their magnitudes. */
-			for (i = 0; i < 3; i++) {
-				if (cloth1->verts[collpair->ap1].impulse_count > 0 && ABS(cloth1->verts[collpair->ap1].impulse[i]) < ABS(i1[i]))
-					cloth1->verts[collpair->ap1].impulse[i] = i1[i];
+			if (cloth1->verts[collpair->ap1].impulse_count > 0) {
+				insert_impulse_in_cluster_array(&vert_imp_clusters[collpair->ap1], i1);
+			}
 
-				if (cloth1->verts[collpair->ap2].impulse_count > 0 && ABS(cloth1->verts[collpair->ap2].impulse[i]) < ABS(i2[i]))
-					cloth1->verts[collpair->ap2].impulse[i] = i2[i];
+			if (cloth1->verts[collpair->ap2].impulse_count > 0) {
+				insert_impulse_in_cluster_array(&vert_imp_clusters[collpair->ap2], i2);
+			}
 
-				if (cloth1->verts[collpair->ap3].impulse_count > 0 && ABS(cloth1->verts[collpair->ap3].impulse[i]) < ABS(i3[i]))
-					cloth1->verts[collpair->ap3].impulse[i] = i3[i];
+			if (cloth1->verts[collpair->ap3].impulse_count > 0) {
+				insert_impulse_in_cluster_array(&vert_imp_clusters[collpair->ap3], i3);
 			}
 		}
 	}
@@ -963,28 +1107,34 @@ static int cloth_bvh_objcollisions_resolve (ClothModifierData * clmd, CollisionM
 	Cloth *cloth = clmd->clothObject;
 	int i=0, j = 0, /*numfaces = 0, */ mvert_num = 0;
 	ClothVertex *verts = NULL;
+	ImpulseCluster **vert_imp_clusters;
 	int ret = 0;
 	int result = 0;
 
 	mvert_num = clmd->clothObject->mvert_num;
 	verts = cloth->verts;
-	
+
+	vert_imp_clusters = MEM_callocN(sizeof(*vert_imp_clusters) * mvert_num, "vert_impulse_clusters");
+
 	// 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_collision_response_static(clmd, collmd, collob, collisions, collisions_index);
+			result += cloth_collision_response_static(clmd, collmd, collob, collisions, collisions_index, vert_imp_clusters);
 
 			// apply impulses in parallel
 			if (result) {
 				for (i = 0; i < mvert_num; 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);
-						VECADD ( verts[i].dcvel, verts[i].dcvel, verts[i].impulse);
+						compute_dominant_impulses(&vert_imp_clusters[i], verts[i].impulse, M_PI / 20);
+						free_impulse_clusters(vert_imp_clusters[i]);
+						vert_imp_clusters[i] = NULL;
+
+						madd_v3_v3v3fl(verts[i].tv, verts[i].tv, verts[i].impulse, 0.5f);
+						madd_v3_v3v3fl(verts[i].dcvel, verts[i].dcvel, verts[i].impulse, 0.5f);
 						zero_v3(verts[i].impulse);
 						verts[i].impulse_count = 0;
 
@@ -998,6 +1148,9 @@ static int cloth_bvh_objcollisions_resolve (ClothModifierData * clmd, CollisionM
 			break;
 		}
 	}
+
+	MEM_freeN(vert_imp_clusters);
+
 	return ret;
 }




More information about the Bf-blender-cvs mailing list