Reason of all this work: Commiting my work-in-progress on reviewed collision system (better + general access to kdop, uses less memory, put it into BLI_* namespace and usage defined like existing BLI_kdtree_*). Deleted old kdop.c

1 files changed, 72 insertions, 52 deletions

diff --git a/source/blender/blenkernel/intern/cloth.c b/source/blender/blenkernel/intern/cloth.c
index 4be4434dfda..192ebd90faa 100644
--- a/source/blender/blenkernel/intern/cloth.c
+++ b/source/blender/blenkernel/intern/cloth.c
@@ -45,6 +45,8 @@
 
 #include "BKE_pointcache.h"
 
+#include "BLI_kdopbvh.h"
+
 #ifdef _WIN32
 void tstart ( void )
 {}
@@ -151,13 +153,14 @@ void cloth_init ( ClothModifierData *clmd )
 	clmd->sim_parms->goalfrict = 0.0f;
 }
 
-
-BVH *bvh_build_from_cloth (ClothModifierData *clmd, float epsilon)
+BVHTree *bvhtree_build_from_cloth (ClothModifierData *clmd, float epsilon)
 {
-	unsigned int i = 0;
-	BVH	*bvh=NULL;
+	int i;
+	BVHTree *bvhtree;
 	Cloth *cloth = clmd->clothObject;
-	ClothVertex *verts = NULL;
+	ClothVertex *verts;
+	MFace *mfaces;
+	float co[12];
 
 	if(!clmd)
 		return NULL;
@@ -168,69 +171,86 @@ BVH *bvh_build_from_cloth (ClothModifierData *clmd, float epsilon)
 		return NULL;
 	
 	verts = cloth->verts;
+	mfaces = cloth->mfaces;
 	
 	// in the moment, return zero if no faces there
 	if(!cloth->numfaces)
 		return NULL;
 	
-	bvh = MEM_callocN(sizeof(BVH), "BVH");
-	if (bvh == NULL) 
-	{
-		printf("bvh: Out of memory.\n");
-		return NULL;
-	}
-	
-	// springs = cloth->springs;
-	// numsprings = cloth->numsprings;
-
-	bvh->epsilon = epsilon;
-	bvh->numfaces = cloth->numfaces;
-	bvh->mfaces = cloth->mfaces;
-
-	bvh->numverts = cloth->numverts;
-	
-	bvh->current_x = MEM_callocN ( sizeof ( MVert ) * bvh->numverts, "bvh->current_x" );
+	// create quadtree with k=26
+	bvhtree = BLI_bvhtree_new(cloth->numfaces, epsilon, 4, 26);
 	
-	if (bvh->current_x == NULL) 
+	// fill tree
+	for(i = 0; i < cloth->numfaces; i++, mfaces++)
 	{
-		printf("bvh: Out of memory.\n");
-		MEM_freeN(bvh);
-		return NULL;
-	}
-	
-	for(i = 0; i < bvh->numverts; i++)
-	{
-		VECCOPY(bvh->current_x[i].co, verts[i].tx);
+		VECCOPY(&co[0*3], verts[mfaces->v1].xold);
+		VECCOPY(&co[1*3], verts[mfaces->v2].xold);
+		VECCOPY(&co[2*3], verts[mfaces->v3].xold);
+		
+		if(mfaces->v4)
+			VECCOPY(&co[3*3], verts[mfaces->v4].xold);
+		
+		BLI_bvhtree_insert(bvhtree, i, co, (mfaces->v4 ? 4 : 3));
 	}
 	
-	bvh_build (bvh);
+	// balance tree
+	BLI_bvhtree_balance(bvhtree);
 	
-	return bvh;
+	return bvhtree;
 }
 
-void bvh_update_from_cloth(ClothModifierData *clmd, int moving)
-{
+void bvhtree_update_from_cloth(ClothModifierData *clmd, int moving)
+{	
 	unsigned int i = 0;
 	Cloth *cloth = clmd->clothObject;
-	BVH *bvh = cloth->tree;
+	BVHTree *bvhtree = cloth->bvhtree;
 	ClothVertex *verts = cloth->verts;
+	MFace *mfaces;
+	float co[12], co_moving[12];
+	int ret = 0;
 	
-	if(!bvh)
+	if(!bvhtree)
 		return;
 	
-	if(cloth->numverts!=bvh->numverts)
-		return;
+	mfaces = cloth->mfaces;
 	
-	if(cloth->verts)
+	// update vertex position in bvh tree
+	if(verts && mfaces)
 	{
-		for(i = 0; i < bvh->numverts; i++)
+		for(i = 0; i < cloth->numfaces; i++, mfaces++)
 		{
-			VECCOPY(bvh->current_x[i].co, verts[i].tx);
-			VECCOPY(bvh->current_xold[i].co, verts[i].txold);
+			VECCOPY(&co[0*3], verts[mfaces->v1].txold);
+			VECCOPY(&co[1*3], verts[mfaces->v2].txold);
+			VECCOPY(&co[2*3], verts[mfaces->v3].txold);
+			
+			if(mfaces->v4)
+				VECCOPY(&co[3*3], verts[mfaces->v4].txold);
+		
+			// copy new locations into array
+			if(moving)
+			{
+				// update moving positions
+				VECCOPY(&co_moving[0*3], verts[mfaces->v1].tx);
+				VECCOPY(&co_moving[1*3], verts[mfaces->v2].tx);
+				VECCOPY(&co_moving[2*3], verts[mfaces->v3].tx);
+				
+				if(mfaces->v4)
+					VECCOPY(&co_moving[3*3], verts[mfaces->v4].tx);
+				
+				ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, (mfaces->v4 ? 4 : 3));
+			}
+			else
+			{
+				ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, (mfaces->v4 ? 4 : 3));
+			}
+			
+			// check if tree is already full
+			if(!ret)
+				break;
 		}
+		
+		BLI_bvhtree_update_tree(bvhtree);
 	}
-	
-	bvh_update(bvh, moving);
 }
 
 int modifiers_indexInObject(Object *ob, ModifierData *md_seek);
@@ -541,8 +561,8 @@ void cloth_free_modifier ( Object *ob, ClothModifierData *clmd )
 		cloth->numsprings = 0;
 
 		// free BVH collision tree
-		if ( cloth->tree )
-			bvh_free ( ( BVH * ) cloth->tree );
+		if ( cloth->bvhtree )
+			BLI_bvhtree_free ( cloth->bvhtree );
 
 		// we save our faces for collision objects
 		if ( cloth->mfaces )
@@ -611,8 +631,8 @@ void cloth_free_modifier_extern ( ClothModifierData *clmd )
 		cloth->numsprings = 0;
 
 		// free BVH collision tree
-		if ( cloth->tree )
-			bvh_free ( ( BVH * ) cloth->tree );
+		if ( cloth->bvhtree )
+			BLI_bvhtree_free ( cloth->bvhtree );
 
 		// we save our faces for collision objects
 		if ( cloth->mfaces )
@@ -810,6 +830,7 @@ static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *d
 		VECCOPY ( verts->xold, verts->x );
 		VECCOPY ( verts->xconst, verts->x );
 		VECCOPY ( verts->txold, verts->x );
+		VECCOPY ( verts->tx, verts->x );
 		VecMulf ( verts->v, 0.0f );
 
 		verts->impulse_count = 0;
@@ -845,12 +866,11 @@ static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *d
 	if(!first)
 		implicit_set_positions(clmd);
 
-	clmd->clothObject->tree = bvh_build_from_cloth ( clmd, clmd->coll_parms->epsilon );
-
+	clmd->clothObject->bvhtree = bvhtree_build_from_cloth ( clmd, clmd->coll_parms->epsilon );
+	
 	return 1;
 }
 
-
 static void cloth_from_mesh ( Object *ob, ClothModifierData *clmd, DerivedMesh *dm )
 {
 	unsigned int numverts = dm->getNumVerts ( dm );