Cloth: Collision improvements

This commit includes several performance, stability, and reliability
improvements to cloth collisions.

Most notably:
* The implementation of a new self-collisions system.
* Multithreading of collision detection.
* Implementation of single sided collisions and normal overrides.
* Replacement of the `plNearestPoints` function from Bullet with a
dedicated solution.

Further, this also includes several bug fixes, and algorithmic
improvements.

Reviewed By: brecht

Differential Revision: http://developer.blender.org/D3712

1 files changed, 76 insertions, 81 deletions

diff --git a/source/blender/modifiers/intern/MOD_collision.c b/source/blender/modifiers/intern/MOD_collision.c
index 5a73d62433b..1cef98fbdf2 100644
--- a/source/blender/modifiers/intern/MOD_collision.c
+++ b/source/blender/modifiers/intern/MOD_collision.c
@@ -146,113 +146,108 @@ static void deformVerts(
 
 		mvert_num = mesh_src->totvert;
 
-		if (current_time > collmd->time_xnew) {
-			unsigned int i;
-
-			/* check if mesh has changed */
-			if (collmd->x && (mvert_num != collmd->mvert_num))
+		if (current_time < collmd->time_xnew) {
+			freeData((ModifierData *)collmd);
+		}
+		else if (current_time == collmd->time_xnew) {
+			if (mvert_num != collmd->mvert_num) {
 				freeData((ModifierData *)collmd);
+			}
+		}
 
-			if (collmd->time_xnew == -1000) { /* first time */
-
-				collmd->x = MEM_dupallocN(mesh_src->mvert); /* frame start position */
+		/* check if mesh has changed */
+		if (collmd->x && (mvert_num != collmd->mvert_num))
+			freeData((ModifierData *)collmd);
 
-				for (i = 0; i < mvert_num; i++) {
-					/* we save global positions */
-					mul_m4_v3(ob->obmat, collmd->x[i].co);
-				}
+		if (collmd->time_xnew == -1000) { /* first time */
 
-				collmd->xnew = MEM_dupallocN(collmd->x); // frame end position
-				collmd->current_x = MEM_dupallocN(collmd->x); // inter-frame
-				collmd->current_xnew = MEM_dupallocN(collmd->x); // inter-frame
-				collmd->current_v = MEM_dupallocN(collmd->x); // inter-frame
+			collmd->x = MEM_dupallocN(mesh_src->mvert); /* frame start position */
 
-				collmd->mvert_num = mvert_num;
+			for (uint i = 0; i < mvert_num; i++) {
+				/* we save global positions */
+				mul_m4_v3(ob->obmat, collmd->x[i].co);
+			}
 
-				{
-					const MLoop *mloop = mesh_src->mloop;
-					const MLoopTri *looptri = BKE_mesh_runtime_looptri_ensure(mesh_src);
-					collmd->tri_num = BKE_mesh_runtime_looptri_len(mesh_src);
-					MVertTri *tri = MEM_malloc_arrayN(collmd->tri_num, sizeof(*tri), __func__);
-					BKE_mesh_runtime_verttri_from_looptri(tri, mloop, looptri, collmd->tri_num);
-					collmd->tri = tri;
-				}
+			collmd->xnew = MEM_dupallocN(collmd->x); // frame end position
+			collmd->current_x = MEM_dupallocN(collmd->x); // inter-frame
+			collmd->current_xnew = MEM_dupallocN(collmd->x); // inter-frame
+			collmd->current_v = MEM_dupallocN(collmd->x); // inter-frame
 
-				/* create bounding box hierarchy */
-				collmd->bvhtree = bvhtree_build_from_mvert(
-				        collmd->x,
-				        collmd->tri, collmd->tri_num,
-				        ob->pd->pdef_sboft);
+			collmd->mvert_num = mvert_num;
 
-				collmd->time_x = collmd->time_xnew = current_time;
-				collmd->is_static = true;
+			{
+				const MLoop *mloop = mesh_src->mloop;
+				const MLoopTri *looptri = BKE_mesh_runtime_looptri_ensure(mesh_src);
+				collmd->tri_num = BKE_mesh_runtime_looptri_len(mesh_src);
+				MVertTri *tri = MEM_mallocN(sizeof(*tri) * collmd->tri_num, __func__);
+				BKE_mesh_runtime_verttri_from_looptri(tri, mloop, looptri, collmd->tri_num);
+				collmd->tri = tri;
 			}
-			else if (mvert_num == collmd->mvert_num) {
-				/* put positions to old positions */
-				tempVert = collmd->x;
-				collmd->x = collmd->xnew;
-				collmd->xnew = tempVert;
-				collmd->time_x = collmd->time_xnew;
 
-				memcpy(collmd->xnew, mesh_src->mvert, mvert_num * sizeof(MVert));
+			/* create bounding box hierarchy */
+			collmd->bvhtree = bvhtree_build_from_mvert(
+					collmd->x,
+					collmd->tri, collmd->tri_num,
+					ob->pd->pdef_sboft);
 
-				bool is_static = true;
+			collmd->time_x = collmd->time_xnew = current_time;
+			collmd->is_static = true;
+		}
+		else if (mvert_num == collmd->mvert_num) {
+			/* put positions to old positions */
+			tempVert = collmd->x;
+			collmd->x = collmd->xnew;
+			collmd->xnew = tempVert;
+			collmd->time_x = collmd->time_xnew;
 
-				for (i = 0; i < mvert_num; i++) {
-					/* we save global positions */
-					mul_m4_v3(ob->obmat, collmd->xnew[i].co);
+			memcpy(collmd->xnew, mesh_src->mvert, mvert_num * sizeof(MVert));
 
-					/* detect motion */
-					is_static = is_static && equals_v3v3(collmd->x[i].co, collmd->xnew[i].co);
-				}
+			bool is_static = true;
 
-				memcpy(collmd->current_xnew, collmd->x, mvert_num * sizeof(MVert));
-				memcpy(collmd->current_x, collmd->x, mvert_num * sizeof(MVert));
+			for (uint i = 0; i < mvert_num; i++) {
+				/* we save global positions */
+				mul_m4_v3(ob->obmat, collmd->xnew[i].co);
 
-				/* check if GUI setting has changed for bvh */
-				if (collmd->bvhtree) {
-					if (ob->pd->pdef_sboft != BLI_bvhtree_get_epsilon(collmd->bvhtree)) {
-						BLI_bvhtree_free(collmd->bvhtree);
-						collmd->bvhtree = bvhtree_build_from_mvert(
-						        collmd->current_x,
-						        collmd->tri, collmd->tri_num,
-						        ob->pd->pdef_sboft);
-					}
+				/* detect motion */
+				is_static = is_static && equals_v3v3(collmd->x[i].co, collmd->xnew[i].co);
+			}
 
-				}
+			memcpy(collmd->current_xnew, collmd->x, mvert_num * sizeof(MVert));
+			memcpy(collmd->current_x, collmd->x, mvert_num * sizeof(MVert));
 
-				/* happens on file load (ONLY when i decomment changes in readfile.c) */
-				if (!collmd->bvhtree) {
+			/* check if GUI setting has changed for bvh */
+			if (collmd->bvhtree) {
+				if (ob->pd->pdef_sboft != BLI_bvhtree_get_epsilon(collmd->bvhtree)) {
+					BLI_bvhtree_free(collmd->bvhtree);
 					collmd->bvhtree = bvhtree_build_from_mvert(
-					        collmd->current_x,
-					        collmd->tri, collmd->tri_num,
-					        ob->pd->pdef_sboft);
-				}
-				else if (!collmd->is_static || !is_static) {
-					/* recalc static bounding boxes */
-					bvhtree_update_from_mvert(
-					        collmd->bvhtree,
-					        collmd->current_x, collmd->current_xnew,
-					        collmd->tri, collmd->tri_num,
-					        true);
+							collmd->current_x,
+							collmd->tri, collmd->tri_num,
+							ob->pd->pdef_sboft);
 				}
+			}
 
-				collmd->is_static = is_static;
-				collmd->time_xnew = current_time;
+			/* happens on file load (ONLY when i decomment changes in readfile.c) */
+			if (!collmd->bvhtree) {
+				collmd->bvhtree = bvhtree_build_from_mvert(
+						collmd->current_x,
+						collmd->tri, collmd->tri_num,
+						ob->pd->pdef_sboft);
 			}
-			else if (mvert_num != collmd->mvert_num) {
-				freeData((ModifierData *)collmd);
+			else if (!collmd->is_static || !is_static) {
+				/* recalc static bounding boxes */
+				bvhtree_update_from_mvert(
+						collmd->bvhtree,
+						collmd->current_x, collmd->current_xnew,
+						collmd->tri, collmd->tri_num,
+						true);
 			}
 
+			collmd->is_static = is_static;
+			collmd->time_xnew = current_time;
 		}
-		else if (current_time < collmd->time_xnew) {
+		else if (mvert_num != collmd->mvert_num) {
 			freeData((ModifierData *)collmd);
 		}
-		else {
-			if (mvert_num != collmd->mvert_num) {
-				freeData((ModifierData *)collmd);
-			}
-		}
 	}
 
 	if (mesh_src != mesh) {