Collisions: Commit of collision cleanup, put kdop-bvh structure into BLI_kdopbvh (just like kdtree interface now), huge speedup for selfcollisions, also better normal collisions (merge from cloth branch)

1 files changed, 16 insertions, 74 deletions

diff --git a/source/blender/blenkernel/BKE_collision.h b/source/blender/blenkernel/BKE_collision.h
index 7328f9108e3..b38bf8662d7 100644
--- a/source/blender/blenkernel/BKE_collision.h
+++ b/source/blender/blenkernel/BKE_collision.h
@@ -24,7 +24,7 @@
  *
  * The Original Code is: all of this file.
  *
- * Contributor(s): none yet.
+ * Contributor(s): Daniel Genrich
  *
  * ***** END GPL LICENSE BLOCK *****
  */
@@ -32,7 +32,7 @@
 #define BKE_COLLISIONS_H
 
 #include <math.h>
-#include "float.h"
+#include <float.h>
 #include <stdlib.h>
 #include <string.h>
 
@@ -47,68 +47,27 @@
 #include "DNA_modifier_types.h"
 #include "DNA_object_types.h"
 
+#include "BLI_kdopbvh.h"
+
 struct Object;
 struct Cloth;
 struct MFace;
 struct DerivedMesh;
 struct ClothModifierData;
-struct CollisionTree;
-
 
 ////////////////////////////////////////
-// used in kdop.c and collision.c
+// used for collisions in collision.c
 ////////////////////////////////////////
-typedef struct CollisionTree
-{
-	struct CollisionTree *nodes[4]; // 4 children --> quad-tree
-	struct CollisionTree *parent;
-	struct CollisionTree *nextLeaf;
-	struct CollisionTree *prevLeaf;
-	float	bv[26]; // Bounding volume of all nodes / we have 7 axes on a 14-DOP
-	unsigned int tri_index; // this saves the index of the face
-	// int point_index[4]; // supports up to 4 points in a leaf
-	int	count_nodes; // how many nodes are used
-	int	traversed;  // how many nodes already traversed until this level?
-	int	isleaf;
-	float alpha; /* for selfcollision */
-	float normal[3]; /* for selfcollision */
-}
-CollisionTree;
 
-typedef struct BVH
+/* COLLISION FLAGS */
+typedef enum
 {
-	unsigned int 	numfaces;
-	unsigned int 	numverts;
-	MVert 		*current_x; // e.g. txold in clothvertex
-	MVert 		*current_xold; // e.g. tx in clothvertex
-	MFace 		*mfaces; // just a pointer to the original datastructure
-	struct LinkNode *tree;
-	CollisionTree 	*root; // TODO: saving the root --> is this really needed? YES!
-	CollisionTree 	*leaf_tree; /* Tail of the leaf linked list.	*/
-	CollisionTree 	*leaf_root;	/* Head of the leaf linked list.	*/
-	float 		epsilon; /* epslion is used for inflation of the k-dop	   */
-	int 		flags; /* bvhFlags */
-}
-BVH;
-////////////////////////////////////////
+	COLLISION_IN_FUTURE = ( 1 << 1 ),
+} COLLISION_FLAGS;
 
 
-
-////////////////////////////////////////
-// kdop.c
 ////////////////////////////////////////
-
-// needed for collision.c
-typedef void ( *CM_COLLISION_RESPONSE ) ( ModifierData *md1, ModifierData *md2, CollisionTree *tree1, CollisionTree *tree2 );
-
-// needed for collision.c
-int bvh_traverse ( ModifierData * md1, ModifierData * md2, CollisionTree * tree1, CollisionTree * tree2, float step, CM_COLLISION_RESPONSE collision_response, int selfcollision);
-
-////////////////////////////////////////
-
-
-////////////////////////////////////////
-// used for collisions in kdop.c and also collision.c
+// used for collisions in collision.c
 ////////////////////////////////////////
 /* used for collisions in collision.c */
 typedef struct CollPair
@@ -119,10 +78,10 @@ typedef struct CollPair
 	float normal[3];
 	float vector[3]; // unnormalized collision vector: p2-p1
 	float pa[3], pb[3]; // collision point p1 on face1, p2 on face2
-	int lastsign; // indicates if the distance sign has changed, unused itm
+	int flag;
 	float time; // collision time, from 0 up to 1
-	unsigned int ap1, ap2, ap3, bp1, bp2, bp3;
-	unsigned int pointsb[4];
+	int ap1, ap2, ap3, bp1, bp2, bp3;
+	int pointsb[4];
 }
 CollPair;
 
@@ -157,32 +116,15 @@ FaceCollPair;
 // forward declarations
 /////////////////////////////////////////////////
 
-// NOTICE: mvert-routines for building + update the BVH are the most native ones
-
-// builds bounding volume hierarchy
-void bvh_build (BVH *bvh);
-BVH *bvh_build_from_mvert (MFace *mfaces, unsigned int numfaces, MVert *x, unsigned int numverts, float epsilon);
-
-// frees the same
-void bvh_free ( BVH * bvh );
-
-// checks two bounding volume hierarchies for potential collisions and returns some list with those
-
-
-// update bounding volumes, needs updated positions in  bvh->current_xold (static) 
-// and also bvh->current_x if moving==1
-void bvh_update_from_mvert(BVH * bvh, MVert *x, unsigned int numverts, MVert *xnew, int moving);
-void bvh_update(BVH * bvh, int moving);
-
 LinkNode *BLI_linklist_append_fast ( LinkNode **listp, void *ptr );
 
 // move Collision modifier object inter-frame with step = [0,1]
 // defined in collisions.c
-void collision_move_object(CollisionModifierData *collmd, float step, float prevstep);
+void collision_move_object ( CollisionModifierData *collmd, float step, float prevstep );
 
 // interface for collision functions
-void collisions_compute_barycentric (float pv[3], float p1[3], float p2[3], float p3[3], float *w1, float *w2, float *w3);
-void interpolateOnTriangle(float to[3], float v1[3], float v2[3], float v3[3], double w1, double w2, double w3);
+void collisions_compute_barycentric ( float pv[3], float p1[3], float p2[3], float p3[3], float *w1, float *w2, float *w3 );
+void interpolateOnTriangle ( float to[3], float v1[3], float v2[3], float v3[3], double w1, double w2, double w3 );
 
 /////////////////////////////////////////////////