[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [12626] branches/particles/source/blender:

Brecht Van Lommel brechtvanlommel at pandora.be
Mon Nov 19 19:31:32 CET 2007


Revision: 12626
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=12626
Author:   blendix
Date:     2007-11-19 19:31:32 +0100 (Mon, 19 Nov 2007)

Log Message:
-----------

Particle Branch
===============

- Added a "Puff" tool to make hairs stand up more, or less.
- Made Shrink and Grow a single tool called "Length", with buttons
  and shift key modifier to switch between the two.
- Partial path cache updates for children and parents, makes editing
  with child particles showing much faster.
- Moved the kdtree code into blenlib, added balancing and optimized
  the nearest neighbour search a bit as well. Makes child particle
  distribution about 3-4 times faster here.
- Take normal into account for child particle parent search (just
  multiply the distance by 10 if the normal is facing away), solves
  issue with parent particles on one side of an ear affecting the other
  side.
- Set dmcache_index in the add brush and mirror tools, otherwise it
  falls back to slow lookups until the cache is refreshed.
- Draw child particles shaded in edit mode, instead of black (they often
  still end up black though, with the normals facing down).
- Fix memory leak when deleting all particles in particle mode.

Modified Paths:
--------------
    branches/particles/source/blender/blenkernel/BKE_particle.h
    branches/particles/source/blender/blenkernel/intern/modifier.c
    branches/particles/source/blender/blenkernel/intern/particle.c
    branches/particles/source/blender/blenkernel/intern/particle_system.c
    branches/particles/source/blender/makesdna/DNA_scene_types.h
    branches/particles/source/blender/src/buttons_editing.c
    branches/particles/source/blender/src/drawobject.c
    branches/particles/source/blender/src/editparticle.c

Added Paths:
-----------
    branches/particles/source/blender/blenlib/BLI_kdtree.h
    branches/particles/source/blender/blenlib/intern/BLI_kdtree.c

Modified: branches/particles/source/blender/blenkernel/BKE_particle.h
===================================================================
--- branches/particles/source/blender/blenkernel/BKE_particle.h	2007-11-19 18:00:48 UTC (rev 12625)
+++ branches/particles/source/blender/blenkernel/BKE_particle.h	2007-11-19 18:31:32 UTC (rev 12626)
@@ -53,19 +53,8 @@
 struct MVert;
 struct IpoCurve;
 struct LinkNode;
+struct KDTree;
 
-typedef struct KDTreeNode{
-	struct KDTreeNode *left, *right;
-	float co[3];
-	int nbr;
-	short d;
-} KDTreeNode;
-
-typedef struct KDTreeNearest {
-	int num;
-	float dist, co[3];
-} KDTreeNearest;
-
 typedef struct ParticleEffectorCache {
 	struct ParticleEffectorCache *next, *prev;
 	struct Object *ob;
@@ -79,7 +68,7 @@
 	float *face_minmax;
 	float *vert_cos;
 	/* precalculated variables for boids */
-	struct KDTreeNode *tree;
+	struct KDTree *tree;
 
 	short type, psys_nbr;
 	
@@ -141,7 +130,7 @@
 typedef struct ParticleUndo {
 	struct ParticleUndo *next, *prev;
 	struct ParticleEditKey **keys;
-	struct KDTreeNode *emitter_field;
+	struct KDTree *emitter_field;
 	struct ParticleData *particles;
 	float *emitter_cosnos;
 	int totpart, totkeys;
@@ -151,7 +140,7 @@
 typedef struct ParticleEdit{
 	ListBase undo;
 	struct ParticleUndo *curundo;
-	struct KDTreeNode *emitter_field;
+	struct KDTree *emitter_field;
 	ParticleEditKey **keys;
 	int *mirror_cache;
 	float *emitter_cosnos;
@@ -201,8 +190,8 @@
 
 void psys_find_parents(struct Object *ob, struct ParticleSystemModifierData *psmd, struct ParticleSystem *psys);
 
-void psys_cache_paths(struct Object *ob, struct ParticleSystem *psys, float cfra);
-void cache_psys_child_paths(struct Object *ob, struct ParticleSystem *psys, float cfra);
+void psys_cache_paths(struct Object *ob, struct ParticleSystem *psys, float cfra, int editupdate);
+void psys_cache_child_paths(struct Object *ob, struct ParticleSystem *psys, float cfra, int editupdate);
 int do_guide(struct ParticleKey *state, int pa_num, float time, struct ListBase *lb);
 float psys_get_size(struct Object *ob, struct Material *ma, struct ParticleSystemModifierData *psmd, struct IpoCurve *icu_size, struct ParticleSystem *psys, struct ParticleSettings *part, struct ParticleData *pa, float *vg_size);
 float psys_get_timestep(struct ParticleSettings *part);
@@ -231,13 +220,6 @@
 void psys_mat_hair_to_object(struct Object *ob, struct DerivedMesh *dm, short from, struct ParticleData *pa, float hairmat[][4]);
 void psys_mat_hair_to_global(struct Object *ob, struct DerivedMesh *dm, short from, struct ParticleData *pa, float hairmat[][4]);
 
-struct KDTreeNode *alloc_kdtree(int nodes);
-struct KDTreeNode *copy_kdtree(struct KDTreeNode *from);
-void free_kdtree(struct KDTreeNode *root);
-int find_nearest_in_kdtree(struct KDTreeNode *root, float *co);
-void insert_into_kdtree(struct KDTreeNode *root, struct KDTreeNode *node);
-int find_n_nearest_in_kdtree(struct KDTreeNode *root, float *co, int n, struct KDTreeNearest *ptn);
-
 float *psys_cache_vgroup(struct DerivedMesh *dm, struct ParticleSystem *psys, int vgroup);
 void psys_get_texture(struct Object *ob, struct Material *ma, struct ParticleSystemModifierData *psmd, struct ParticleSystem *psys, struct ParticleData *pa, struct ParticleTexture *ptex, int event);
 void psys_interpolate_face(struct MVert *mvert, struct MFace *mface, struct MTFace *tface, float *uv, float *vec, float *nor, float *utan, float *vtan);

Modified: branches/particles/source/blender/blenkernel/intern/modifier.c
===================================================================
--- branches/particles/source/blender/blenkernel/intern/modifier.c	2007-11-19 18:00:48 UTC (rev 12625)
+++ branches/particles/source/blender/blenkernel/intern/modifier.c	2007-11-19 18:31:32 UTC (rev 12626)
@@ -41,10 +41,11 @@
 #include "math.h"
 #include "float.h"
 
+#include "BLI_arithb.h"
 #include "BLI_blenlib.h"
+#include "BLI_kdtree.h"
+#include "BLI_linklist.h"
 #include "BLI_rand.h"
-#include "BLI_arithb.h"
-#include "BLI_linklist.h"
 #include "BLI_edgehash.h"
 #include "BLI_ghash.h"
 #include "BLI_memarena.h"
@@ -5385,8 +5386,8 @@
 	MFace *fa=0, *mface=0;
 	MVert *mvert = 0;
 	ParticleData *pa;
-	KDTreeNode *tree, *cur;
-	float center[3];
+	KDTree *tree;
+	float center[3], co[3];
 	int *facepa=0,*vertpa=0,totvert=0,totface=0,totpart=0;
 	int i,p,v1,v2,v3,v4=0;
 
@@ -5427,12 +5428,12 @@
 	}
 
 	/* make tree of emitter locations */
-	tree=alloc_kdtree(totpart);
-	for(p=0,pa=psys->particles,cur=tree; p<totpart; p++,pa++,cur++){
-		psys_particle_on_dm(ob,dm,psys->part->from,pa->num,pa->num_dmcache,pa->fuv,pa->foffset,cur->co,0,0,0);
-		cur->nbr=p;
-		if(p) insert_into_kdtree(tree,cur);
+	tree=BLI_kdtree_new(totpart);
+	for(p=0,pa=psys->particles; p<totpart; p++,pa++){
+		psys_particle_on_dm(ob,dm,psys->part->from,pa->num,pa->num_dmcache,pa->fuv,pa->foffset,co,0,0,0);
+		BLI_kdtree_insert(tree, p, co, NULL);
 	}
+	BLI_kdtree_balance(tree);
 
 	/* set face-particle-indexes to nearest particle to face center */
 	for(i=0,fa=mface; i<totface; i++,fa++){
@@ -5445,7 +5446,7 @@
 		else
 			VecMulf(center,0.3333f);
 
-		p=find_nearest_in_kdtree(tree,center);
+		p= BLI_kdtree_find_nearest(tree,center,NULL,NULL);
 
 		v1=vertpa[fa->v1];
 		v2=vertpa[fa->v2];
@@ -5463,7 +5464,7 @@
 	}
 
 	if(vertpa) MEM_freeN(vertpa);
-	free_kdtree(tree);
+	BLI_kdtree_free(tree);
 }
 static DerivedMesh * explodeModifier_splitEdges(ExplodeModifierData *emd, DerivedMesh *dm){
 	DerivedMesh *splitdm;

Modified: branches/particles/source/blender/blenkernel/intern/particle.c
===================================================================
--- branches/particles/source/blender/blenkernel/intern/particle.c	2007-11-19 18:00:48 UTC (rev 12625)
+++ branches/particles/source/blender/blenkernel/intern/particle.c	2007-11-19 18:31:32 UTC (rev 12626)
@@ -51,11 +51,12 @@
 #include "DNA_key_types.h"
 #include "DNA_bake_types.h"
 
-#include "BLI_rand.h"
 #include "BLI_arithb.h"
 #include "BLI_blenlib.h"
 #include "BLI_dynstr.h"
+#include "BLI_kdtree.h"
 #include "BLI_linklist.h"
+#include "BLI_rand.h"
 
 #include "BKE_anim.h"
 
@@ -255,10 +256,6 @@
 	if(part->pd)
 		MEM_freeN(part->pd);
 }
-void free_kdtree(KDTreeNode *root){
-	if(root)
-		MEM_freeN(root);
-}
 void free_hair(ParticleSystem *psys)
 {
 	ParticleData *pa;
@@ -346,205 +343,7 @@
 		MEM_freeN(psys);
 	}
 }
-/************************************************/
-/*			KD Tree								*/
-/************************************************/
-KDTreeNode *alloc_kdtree(int nodes){
-	return MEM_callocN(nodes*sizeof(KDTreeNode), "KD tree nodes");
-}
-KDTreeNode *copy_kdtree(KDTreeNode *from)
-{
-	KDTreeNode *tn, *to = MEM_dupallocN(from);
-	int i, size=MEM_allocN_len(from)/sizeof(KDTreeNode);
-	
-	for(i=0,tn=to; i<size; i++,tn++){
-		/* from & to are most probably not aligned in memory with			*/
-		/* ParticleTreeNode size so we can't use simple "tn->left+=to-from" */
-		if(tn->left)
-			tn->left=to+(tn->left-from);
-		if(tn->right)
-			tn->right=to+(tn->right-from);
-	}
-	return to;
-}
-/* needs to be coded better to create balanced trees & range searching */
-/* now just a quickie to get things rolling */
-void insert_into_kdtree(KDTreeNode *root, KDTreeNode *node){
-	KDTreeNode *cur_node=root;
-	int d=0, not_done=1;
 
-	while(not_done){
-		if(node->co[d%3] < cur_node->co[d%3]){
-			if(cur_node->left){
-				cur_node=cur_node->left;
-				d++;
-			}
-			else{
-				node->d=(short)((d+1)%3);
-				cur_node->left=node;
-				not_done=0;
-			}
-		}
-		else{
-			if(cur_node->right){
-				cur_node=cur_node->right;
-				d++;
-			}
-			else{
-				node->d=(short)((d+1)%3);
-				cur_node->right=node;
-				not_done=0;
-			}
-		}
-	}
-}
-/* finds the nearest entry in tree to specified coordinates */
-int find_nearest_in_kdtree(KDTreeNode *root, float *co)
-{
-	KDTreeNode *cur_node=0;
-	int totstack=100, cur=0;
-	int *stack;
-	float min_dist, cur_dist;
-	int min_num=root->nbr;
-
-	if(root->nbr==-1)
-		return -1;
-	else
-		stack=MEM_callocN(100*sizeof(int), "psys_treestack");
-	
-	min_dist= VecLenf(root->co,co);
-
-	if(root->left)
-		stack[cur++]=root->left->nbr;
-
-	if(root->right)
-		stack[cur++]=root->right->nbr;
-
-	while(cur--){
-		cur_node=root+stack[cur];
-
-		cur_dist = cur_node->co[cur_node->d] - co[cur_node->d];
-
-		if(cur_dist<0.0){
-			if(-cur_dist<min_dist){
-				cur_dist=VecLenf(cur_node->co,co);
-				if(cur_dist<min_dist){
-					min_dist=cur_dist;
-					min_num=cur_node->nbr;
-				}
-				if(cur_node->left)
-					stack[cur++]=cur_node->left->nbr;
-			}
-			if(cur_node->right)
-				stack[cur++]=cur_node->right->nbr;
-		}
-		else{
-			if(cur_dist<min_dist){
-				cur_dist=VecLenf(cur_node->co,co);
-				if(cur_dist<min_dist){
-					min_dist=cur_dist;
-					min_num=cur_node->nbr;
-				}
-				if(cur_node->right)
-					stack[cur++]=cur_node->right->nbr;
-			}
-			if(cur_node->left)
-				stack[cur++]=cur_node->left->nbr;
-		}
-		if(cur+3 > totstack){
-			int *temp=MEM_callocN((totstack+100)*sizeof(int), "psys_treestack");
-			memcpy(temp,stack,totstack*sizeof(int));
-			MEM_freeN(stack);
-			stack=temp;
-			totstack+=100;
-		}
-	}
-
-	MEM_freeN(stack);
-	return min_num;
-}
-static int ptnearsort(const void *v1, const void *v2)
-{
-	const struct KDTreeNearest *x1=v1, *x2=v2;
-
-	if( x1->dist > x2->dist) return 1;
-	else if( x1->dist < x2->dist) return -1;
-	
-	return 0;
-}
-static void add_ptn(KDTreeNearest *ptn, int *found, int n, int nbr, float dist, float *co)
-{
-	if(*found<n) (*found)++;
-
-	ptn[*found-1].num=nbr;
-	ptn[*found-1].dist=dist;
-	VecCopyf(ptn[*found-1].co,co);
-
-	qsort(ptn, *found, sizeof(struct KDTreeNearest), ptnearsort);
-}
-/* finds the nearest n entries in tree to specified coordinates */
-int find_n_nearest_in_kdtree(KDTreeNode *root, float *co, int n, KDTreeNearest *ptn)
-{
-	KDTreeNode *cur_node=0;
-	int totstack=100, cur=0;
-	int *stack=0;
-	float cur_dist;
-	int found=0;
-
-	if(root->nbr==-1)
-		return 0;
-	else
-		stack=MEM_callocN(100*sizeof(int), "Particle Tree Stack");
-
-	add_ptn(ptn,&found,n,root->nbr,VecLenf(root->co,co),root->co);
-	
-	if(root->left)
-		stack[cur++]=root->left->nbr;
-
-	if(root->right)
-		stack[cur++]=root->right->nbr;
-
-	while(cur--){
-		cur_node=root+stack[cur];
-
-		cur_dist = cur_node->co[cur_node->d] - co[cur_node->d];
-
-		if(cur_dist<0.0){
-			if(found<n || -cur_dist<ptn[found-1].dist){
-				cur_dist=VecLenf(cur_node->co,co);
-				if(found<n || cur_dist<ptn[found-1].dist)
-					add_ptn(ptn,&found,n,cur_node->nbr,cur_dist,cur_node->co);
-
-				if(cur_node->left)
-					stack[cur++]=cur_node->left->nbr;
-			}

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list