[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15101] trunk/blender/source/blender: 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)
Daniel Genrich
daniel.genrich at gmx.net
Tue Jun 3 20:48:54 CEST 2008
Revision: 15101
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15101
Author: genscher
Date: 2008-06-03 20:48:54 +0200 (Tue, 03 Jun 2008)
Log Message:
-----------
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)
Modified Paths:
--------------
trunk/blender/source/blender/blenkernel/BKE_cloth.h
trunk/blender/source/blender/blenkernel/BKE_collision.h
trunk/blender/source/blender/blenkernel/intern/cloth.c
trunk/blender/source/blender/blenkernel/intern/collision.c
trunk/blender/source/blender/blenkernel/intern/kdop.c
trunk/blender/source/blender/blenkernel/intern/modifier.c
trunk/blender/source/blender/blenloader/intern/readfile.c
trunk/blender/source/blender/makesdna/DNA_modifier_types.h
Modified: trunk/blender/source/blender/blenkernel/BKE_cloth.h
===================================================================
--- trunk/blender/source/blender/blenkernel/BKE_cloth.h 2008-06-03 16:43:07 UTC (rev 15100)
+++ trunk/blender/source/blender/blenkernel/BKE_cloth.h 2008-06-03 18:48:54 UTC (rev 15101)
@@ -24,14 +24,14 @@
*
* The Original Code is: all of this file.
*
- * Contributor(s): none yet.
+ * Contributor(s): Daniel Genrich
*
* ***** END GPL LICENSE BLOCK *****
*/
#ifndef BKE_CLOTH_H
#define BKE_CLOTH_H
-#include "float.h"
+#include <float.h>
#include "BLI_linklist.h"
#include "BKE_customdata.h"
@@ -102,7 +102,8 @@
unsigned char old_solver_type; /* unused, only 1 solver here */
unsigned char pad2;
short pad3;
- struct BVH *tree; /* collision tree for this cloth object */
+ struct BVHTree *bvhtree; /* collision tree for this cloth object */
+ struct BVHTree *bvhselftree; /* collision tree for this cloth object */
struct MFace *mfaces;
struct Implicit_Data *implicit; /* our implicit solver connects to this pointer */
struct Implicit_Data *implicitEM; /* our implicit solver connects to this pointer */
@@ -171,17 +172,10 @@
/* These are the bits used in SimSettings.flags. */
typedef enum
{
- //CLOTH_SIMSETTINGS_FLAG_RESET = ( 1 << 1 ), // The CM object requires a reinitializaiton.
CLOTH_SIMSETTINGS_FLAG_COLLOBJ = ( 1 << 2 ),// object is only collision object, no cloth simulation is done
CLOTH_SIMSETTINGS_FLAG_GOAL = ( 1 << 3 ), // we have goals enabled
CLOTH_SIMSETTINGS_FLAG_TEARING = ( 1 << 4 ),// true if tearing is enabled
- //CLOTH_SIMSETTINGS_FLAG_CCACHE_PROTECT = ( 1 << 5 ), // true if tearing is enabled
- //CLOTH_SIMSETTINGS_FLAG_EDITMODE = ( 1 << 6 ), // are we in editmode? -several things disabled
- //CLOTH_SIMSETTINGS_FLAG_CCACHE_FFREE = ( 1 << 7 ), /* force cache freeing */
CLOTH_SIMSETTINGS_FLAG_SCALING = ( 1 << 8 ), /* is advanced scaling active? */
- //CLOTH_SIMSETTINGS_FLAG_LOADED = ( 1 << 9 ), /* did we just got load? */
- //CLOTH_SIMSETTINGS_FLAG_AUTOPROTECT = ( 1 << 10 ), /* is autoprotect enabled? */
- //CLOTH_SIMSETTINGS_FLAG_CCACHE_OUTDATED = (1 << 11), /* while protected, did cache get outdated? */
CLOTH_SIMSETTINGS_FLAG_CCACHE_EDIT = (1 << 12) /* edit cache in editmode */
} CLOTH_SIMSETTINGS_FLAGS;
@@ -208,6 +202,7 @@
CLOTH_SPRING_FLAG_NEEDED = ( 1 << 2 ), // springs has values to be applied
} CLOTH_SPRINGS_FLAGS;
+
/////////////////////////////////////////////////
// collision.c
////////////////////////////////////////////////
@@ -246,7 +241,8 @@
void cloth_update_normals ( ClothVertex *verts, int nVerts, MFace *face, int totface );
// needed for collision.c
-void bvh_update_from_cloth ( ClothModifierData *clmd, int moving );
+void bvhtree_update_from_cloth ( ClothModifierData *clmd, int moving );
+void bvhselftree_update_from_cloth ( ClothModifierData *clmd, int moving );
// needed for editmesh.c
void cloth_write_cache ( Object *ob, ClothModifierData *clmd, float framenr );
@@ -261,11 +257,6 @@
////////////////////////////////////////////////
-/* Typedefs for function pointers we need for solvers and collision detection. */
-typedef void ( *CM_COLLISION_SELF ) ( ClothModifierData *clmd, int step );
-typedef void ( *CM_COLLISION_OBJ ) ( ClothModifierData *clmd, int step, CM_COLLISION_RESPONSE collision_response );
-
-
/* This enum provides the IDs for our solvers. */
// only one available in the moment
typedef enum
@@ -286,15 +277,6 @@
}
CM_SOLVER_DEF;
-/* used for caching in implicit.c */
-typedef struct Frame
-{
- ClothVertex *verts;
- ClothSpring *springs;
- unsigned int numverts, numsprings;
- float time; /* we need float since we want to support sub-frames */
-}
-Frame;
#endif
Modified: trunk/blender/source/blender/blenkernel/BKE_collision.h
===================================================================
--- trunk/blender/source/blender/blenkernel/BKE_collision.h 2008-06-03 16:43:07 UTC (rev 15100)
+++ trunk/blender/source/blender/blenkernel/BKE_collision.h 2008-06-03 18:48:54 UTC (rev 15101)
@@ -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,69 +47,28 @@
#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
+// used for collisions in collision.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 */
typedef struct CollPair
{
@@ -119,10 +78,10 @@
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 @@
// 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 );
/////////////////////////////////////////////////
Modified: trunk/blender/source/blender/blenkernel/intern/cloth.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/cloth.c 2008-06-03 16:43:07 UTC (rev 15100)
+++ trunk/blender/source/blender/blenkernel/intern/cloth.c 2008-06-03 18:48:54 UTC (rev 15101)
@@ -45,6 +45,8 @@
#include "BKE_pointcache.h"
+#include "BLI_kdopbvh.h"
+
#ifdef _WIN32
void tstart ( void )
{}
@@ -151,13 +153,14 @@
clmd->sim_parms->goalfrict = 0.0f;
}
-
-BVH *bvh_build_from_cloth (ClothModifierData *clmd, float epsilon)
+BVHTree *bvhselftree_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,171 @@
return NULL;
verts = cloth->verts;
+ mfaces = cloth->mfaces;
// in the moment, return zero if no faces there
- if(!cloth->numfaces)
+ if(!cloth->numverts)
return NULL;
- bvh = MEM_callocN(sizeof(BVH), "BVH");
- if (bvh == NULL)
+ // create quadtree with k=26
+ bvhtree = BLI_bvhtree_new(cloth->numverts, epsilon, 4, 6);
+
+ // fill tree
+ for(i = 0; i < cloth->numverts; i++, verts++)
{
- printf("bvh: Out of memory.\n");
- return NULL;
+ VECCOPY(&co[0*3], verts->xold);
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list