diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-09-02 00:17:56 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-09-02 00:17:56 +0400 |
commit | 36065ee4f4a729ab48df5388373c26b07554de67 (patch) | |
tree | ea5abc0de5357a1e49120a139ef2f62270bc0bd3 | |
parent | 77e86dce2aa868f96467b1989f905cf9cb20de02 (diff) |
use strict flags for kdtree, and replace ints with unsigned ints where possible.
also replace callocs with mallocs since zeroing memory can be avoided.
-rw-r--r-- | source/blender/blenkernel/intern/boids.c | 20 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/dynamicpaint.c | 5 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/particle_system.c | 4 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_kdtree.h | 33 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdtree.c | 121 | ||||
-rw-r--r-- | source/blender/editors/physics/particle_edit.c | 4 |
6 files changed, 115 insertions, 72 deletions
diff --git a/source/blender/blenkernel/intern/boids.c b/source/blender/blenkernel/intern/boids.c index cf761bf3dab..8ce84609c15 100644 --- a/source/blender/blenkernel/intern/boids.c +++ b/source/blender/blenkernel/intern/boids.c @@ -253,7 +253,8 @@ static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues * //check boids in own system if (acbr->options & BRULE_ACOLL_WITH_BOIDS) { - neighbors = BLI_kdtree_range_search(bbd->sim->psys->tree, acbr->look_ahead * len_v3(pa->prev_state.vel), pa->prev_state.co, pa->prev_state.ave, &ptn); + neighbors = BLI_kdtree_range_search(bbd->sim->psys->tree, pa->prev_state.co, pa->prev_state.ave, + &ptn, acbr->look_ahead * len_v3(pa->prev_state.vel)); if (neighbors > 1) for (n=1; n<neighbors; n++) { copy_v3_v3(co1, pa->prev_state.co); copy_v3_v3(vel1, pa->prev_state.vel); @@ -299,7 +300,8 @@ static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues * ParticleSystem *epsys = psys_get_target_system(bbd->sim->ob, pt); if (epsys) { - neighbors = BLI_kdtree_range_search(epsys->tree, acbr->look_ahead * len_v3(pa->prev_state.vel), pa->prev_state.co, pa->prev_state.ave, &ptn); + neighbors = BLI_kdtree_range_search(epsys->tree, pa->prev_state.co, pa->prev_state.ave, + &ptn, acbr->look_ahead * len_v3(pa->prev_state.vel)); if (neighbors > 0) for (n=0; n<neighbors; n++) { copy_v3_v3(co1, pa->prev_state.co); copy_v3_v3(vel1, pa->prev_state.vel); @@ -354,7 +356,8 @@ static int rule_separate(BoidRule *UNUSED(rule), BoidBrainData *bbd, BoidValues ParticleTarget *pt; float len = 2.0f * val->personal_space * pa->size + 1.0f; float vec[3] = {0.0f, 0.0f, 0.0f}; - int neighbors = BLI_kdtree_range_search(bbd->sim->psys->tree, 2.0f * val->personal_space * pa->size, pa->prev_state.co, NULL, &ptn); + int neighbors = BLI_kdtree_range_search(bbd->sim->psys->tree, pa->prev_state.co, NULL, + &ptn, 2.0f * val->personal_space * pa->size); int ret = 0; if (neighbors > 1 && ptn[1].dist!=0.0f) { @@ -372,7 +375,8 @@ static int rule_separate(BoidRule *UNUSED(rule), BoidBrainData *bbd, BoidValues ParticleSystem *epsys = psys_get_target_system(bbd->sim->ob, pt); if (epsys) { - neighbors = BLI_kdtree_range_search(epsys->tree, 2.0f * val->personal_space * pa->size, pa->prev_state.co, NULL, &ptn); + neighbors = BLI_kdtree_range_search(epsys->tree, pa->prev_state.co, NULL, + &ptn, 2.0f * val->personal_space * pa->size); if (neighbors > 0 && ptn[0].dist < len) { sub_v3_v3v3(vec, pa->prev_state.co, ptn[0].co); @@ -392,7 +396,7 @@ static int rule_flock(BoidRule *UNUSED(rule), BoidBrainData *bbd, BoidValues *UN { KDTreeNearest ptn[11]; float vec[3] = {0.0f, 0.0f, 0.0f}, loc[3] = {0.0f, 0.0f, 0.0f}; - int neighbors = BLI_kdtree_find_n_nearest(bbd->sim->psys->tree, 11, pa->state.co, pa->prev_state.ave, ptn); + int neighbors = BLI_kdtree_find_nearest_n(bbd->sim->psys->tree, pa->state.co, pa->prev_state.ave, ptn, 11); int n; int ret = 0; @@ -619,7 +623,8 @@ static int rule_fight(BoidRule *rule, BoidBrainData *bbd, BoidValues *val, Parti int n, ret = 0; /* calculate own group strength */ - int neighbors = BLI_kdtree_range_search(bbd->sim->psys->tree, fbr->distance, pa->prev_state.co, NULL, &ptn); + int neighbors = BLI_kdtree_range_search(bbd->sim->psys->tree, pa->prev_state.co, NULL, + &ptn, fbr->distance); for (n=0; n<neighbors; n++) { bpa = bbd->sim->psys->particles[ptn[n].index].boid; health += bpa->data.health; @@ -635,7 +640,8 @@ static int rule_fight(BoidRule *rule, BoidBrainData *bbd, BoidValues *val, Parti if (epsys) { epars = epsys->particles; - neighbors = BLI_kdtree_range_search(epsys->tree, fbr->distance, pa->prev_state.co, NULL, &ptn); + neighbors = BLI_kdtree_range_search(epsys->tree, pa->prev_state.co, NULL, + &ptn, fbr->distance); health = 0.0f; diff --git a/source/blender/blenkernel/intern/dynamicpaint.c b/source/blender/blenkernel/intern/dynamicpaint.c index a62ca530bf9..a6cff9f20fb 100644 --- a/source/blender/blenkernel/intern/dynamicpaint.c +++ b/source/blender/blenkernel/intern/dynamicpaint.c @@ -3802,14 +3802,15 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface, */ KDTreeNearest *nearest; - int n, particles = 0; + int n, particles; float smooth_range = smooth * (1.0f - strength), dist; /* calculate max range that can have particles with higher influence than the nearest one */ float max_range = smooth - strength * smooth + solidradius; /* Make gcc happy! */ dist = max_range; - particles = BLI_kdtree_range_search(tree, max_range, bData->realCoord[bData->s_pos[index]].v, NULL, &nearest); + particles = BLI_kdtree_range_search(tree, bData->realCoord[bData->s_pos[index]].v, NULL, + &nearest, max_range); /* Find particle that produces highest influence */ for (n = 0; n < particles; n++) { diff --git a/source/blender/blenkernel/intern/particle_system.c b/source/blender/blenkernel/intern/particle_system.c index 723b8332ffd..db22e030821 100644 --- a/source/blender/blenkernel/intern/particle_system.c +++ b/source/blender/blenkernel/intern/particle_system.c @@ -815,7 +815,7 @@ static void distribute_threads_exec(ParticleThread *thread, ParticleData *pa, Ch psys_particle_on_dm(ctx->dm,from,pa->num,pa->num_dmcache,pa->fuv,pa->foffset,co1,0,0,0,orco1,0); BKE_mesh_orco_verts_transform((Mesh*)ob->data, &orco1, 1, 1); - maxw = BLI_kdtree_find_n_nearest(ctx->tree,3,orco1,NULL,ptn); + maxw = BLI_kdtree_find_nearest_n(ctx->tree,orco1,NULL,ptn,3); for (w=0; w<maxw; w++) { pa->verts[w]=ptn->num; @@ -940,7 +940,7 @@ static void distribute_threads_exec(ParticleThread *thread, ParticleData *pa, Ch psys_particle_on_dm(dm,cfrom,cpa->num,DMCACHE_ISCHILD,cpa->fuv,cpa->foffset,co1,nor1,NULL,NULL,orco1,NULL); BKE_mesh_orco_verts_transform((Mesh*)ob->data, &orco1, 1, 1); - maxw = BLI_kdtree_find_n_nearest(ctx->tree,4,orco1,NULL,ptn); + maxw = BLI_kdtree_find_nearest_n(ctx->tree,orco1,NULL,ptn,3); maxd=ptn[maxw-1].dist; /* mind=ptn[0].dist; */ /* UNUSED */ diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/BLI_kdtree.h index b687d98e6ad..e3c81021351 100644 --- a/source/blender/blenlib/BLI_kdtree.h +++ b/source/blender/blenlib/BLI_kdtree.h @@ -31,6 +31,8 @@ * \author Brecht van Lommel */ +#include "BLI_compiler_attrs.h" + struct KDTree; typedef struct KDTree KDTree; @@ -40,22 +42,19 @@ typedef struct KDTreeNearest { float co[3]; } KDTreeNearest; -/* Creates or free a kdtree */ -KDTree *BLI_kdtree_new(int maxsize); +KDTree *BLI_kdtree_new(unsigned int maxsize); void BLI_kdtree_free(KDTree *tree); -/* Construction: first insert points, then call balance. Normal is optional. */ -void BLI_kdtree_insert(KDTree *tree, int index, const float co[3], const float nor[3]); -void BLI_kdtree_balance(KDTree *tree); - -/* Find nearest returns index, and -1 if no node is found. - * Find n nearest returns number of points found, with results in nearest. - * Normal is optional, but if given will limit results to points in normal direction from co. */ -int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], KDTreeNearest *nearest); -int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const float nor[3], KDTreeNearest *nearest); - -/* Range search returns number of points found, with results in nearest */ -/* Normal is optional, but if given will limit results to points in normal direction from co. */ -/* Remember to free nearest after use! */ -int BLI_kdtree_range_search(KDTree *tree, float range, const float co[3], const float nor[3], KDTreeNearest **nearest); -#endif +void BLI_kdtree_insert(KDTree *tree, int index, const float co[3], const float nor[3]) ATTR_NONNULL(1, 3); +void BLI_kdtree_balance(KDTree *tree) ATTR_NONNULL(1); + +int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], + KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2); +int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3], + KDTreeNearest *r_nearest, + unsigned int n) ATTR_NONNULL(1, 2, 4); +int BLI_kdtree_range_search(KDTree *tree, const float co[3], const float nor[3], + KDTreeNearest **r_nearest, + float range) ATTR_NONNULL(1, 2, 4) ATTR_WARN_UNUSED_RESULT; + +#endif /* __BLI_KDTREE_H__ */ diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c index 38910534d99..57227dc5d5f 100644 --- a/source/blender/blenlib/intern/BLI_kdtree.c +++ b/source/blender/blenlib/intern/BLI_kdtree.c @@ -30,18 +30,19 @@ #include "BLI_math.h" #include "BLI_kdtree.h" #include "BLI_utildefines.h" +#include "BLI_strict_flags.h" typedef struct KDTreeNode { struct KDTreeNode *left, *right; float co[3], nor[3]; int index; - short d; + unsigned int d; /* range is only (0-2) */ } KDTreeNode; struct KDTree { KDTreeNode *nodes; - int totnode; + unsigned int totnode; KDTreeNode *root; }; @@ -49,13 +50,17 @@ struct KDTree { #define KD_NEAR_ALLOC_INC 100 /* alloc increment for collecting nearest */ #define KD_FOUND_ALLOC_INC 50 /* alloc increment for collecting nearest */ -KDTree *BLI_kdtree_new(int maxsize) +/** + * Creates or free a kdtree + */ +KDTree *BLI_kdtree_new(unsigned int maxsize) { KDTree *tree; - tree = MEM_callocN(sizeof(KDTree), "KDTree"); - tree->nodes = MEM_callocN(sizeof(KDTreeNode) * maxsize, "KDTreeNode"); + tree = MEM_mallocN(sizeof(KDTree), "KDTree"); + tree->nodes = MEM_mallocN(sizeof(KDTreeNode) * maxsize, "KDTreeNode"); tree->totnode = 0; + tree->root = NULL; return tree; } @@ -68,20 +73,32 @@ void BLI_kdtree_free(KDTree *tree) } } +/** + * Construction: first insert points, then call balance. Normal is optional. + */ void BLI_kdtree_insert(KDTree *tree, int index, const float co[3], const float nor[3]) { KDTreeNode *node = &tree->nodes[tree->totnode++]; - node->index = index; + /* note, array isn't calloc'd, + * need to initialize all struct members */ + + node->left = node->right = NULL; copy_v3_v3(node->co, co); - if (nor) copy_v3_v3(node->nor, nor); + if (nor) + copy_v3_v3(node->nor, nor); + else + zero_v3(node->nor); + + node->index = index; + node->d = 0; } -static KDTreeNode *kdtree_balance(KDTreeNode *nodes, int totnode, int axis) +static KDTreeNode *kdtree_balance(KDTreeNode *nodes, unsigned int totnode, unsigned int axis) { KDTreeNode *node; float co; - int left, right, median, i, j; + unsigned int left, right, median, i, j; if (totnode <= 0) return NULL; @@ -102,7 +119,9 @@ static KDTreeNode *kdtree_balance(KDTreeNode *nodes, int totnode, int axis) while (nodes[++i].co[axis] < co) ; while (nodes[--j].co[axis] > co && j > left) ; - if (i >= j) break; + if (i >= j) + break; + SWAP(KDTreeNode, nodes[i], nodes[j]); } @@ -147,23 +166,27 @@ static float squared_distance(const float v2[3], const float v1[3], const float return dist; } -static KDTreeNode **recalloc_nodes(KDTreeNode **stack, int *totstack, const bool is_alloc) +static KDTreeNode **realloc_nodes(KDTreeNode **stack, unsigned int *totstack, const bool is_alloc) { KDTreeNode **stack_new = MEM_mallocN((*totstack + KD_NEAR_ALLOC_INC) * sizeof(KDTreeNode *), "KDTree.treestack"); memcpy(stack_new, stack, *totstack * sizeof(KDTreeNode *)); - memset(stack_new + *totstack, 0, sizeof(KDTreeNode *) * KD_NEAR_ALLOC_INC); + // memset(stack_new + *totstack, 0, sizeof(KDTreeNode *) * KD_NEAR_ALLOC_INC); if (is_alloc) MEM_freeN(stack); *totstack += KD_NEAR_ALLOC_INC; return stack_new; } -int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], KDTreeNearest *nearest) +/** + * Find nearest returns index, and -1 if no node is found. + */ +int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], + KDTreeNearest *r_nearest) { KDTreeNode *root, *node, *min_node; KDTreeNode **stack, *defaultstack[KD_STACK_INIT]; float min_dist, cur_dist; - int totstack, cur = 0; + unsigned int totstack, cur = 0; if (!tree->root) return -1; @@ -224,14 +247,14 @@ int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], stack[cur++] = node->left; } if (UNLIKELY(cur + 3 > totstack)) { - stack = recalloc_nodes(stack, &totstack, defaultstack != stack); + stack = realloc_nodes(stack, &totstack, defaultstack != stack); } } - if (nearest) { - nearest->index = min_node->index; - nearest->dist = sqrtf(min_dist); - copy_v3_v3(nearest->co, min_node->co); + if (r_nearest) { + r_nearest->index = min_node->index; + r_nearest->dist = sqrtf(min_dist); + copy_v3_v3(r_nearest->co, min_node->co); } if (stack != defaultstack) @@ -240,9 +263,10 @@ int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], return min_node->index; } -static void add_nearest(KDTreeNearest *ptn, int *found, int n, int index, float dist, float *co) +static void add_nearest(KDTreeNearest *ptn, unsigned int *found, unsigned int n, int index, + float dist, const float *co) { - int i; + unsigned int i; if (*found < n) (*found)++; @@ -258,15 +282,23 @@ static void add_nearest(KDTreeNearest *ptn, int *found, int n, int index, float copy_v3_v3(ptn[i].co, co); } -/* finds the nearest n entries in tree to specified coordinates */ -int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const float nor[3], KDTreeNearest *nearest) +/** + * Find n nearest returns number of points found, with results in nearest. + * Normal is optional, but if given will limit results to points in normal direction from co. + * + * \param r_nearest An array of nearest, sized at least \a n. + */ +int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3], + KDTreeNearest r_nearest[], + unsigned int n) { KDTreeNode *root, *node = NULL; KDTreeNode **stack, *defaultstack[KD_STACK_INIT]; float cur_dist; - int i, totstack, cur = 0, found = 0; + unsigned int totstack, cur = 0; + unsigned int i, found = 0; - if (!tree->root) + if (!tree->root || n == 0) return 0; stack = defaultstack; @@ -275,7 +307,7 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const floa root = tree->root; cur_dist = squared_distance(root->co, co, root->nor, nor); - add_nearest(nearest, &found, n, root->index, cur_dist, root->co); + add_nearest(r_nearest, &found, n, root->index, cur_dist, root->co); if (co[root->d] < root->co[root->d]) { if (root->right) @@ -298,11 +330,11 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const floa if (cur_dist < 0.0f) { cur_dist = -cur_dist * cur_dist; - if (found < n || -cur_dist < nearest[found - 1].dist) { + if (found < n || -cur_dist < r_nearest[found - 1].dist) { cur_dist = squared_distance(node->co, co, node->nor, nor); - if (found < n || cur_dist < nearest[found - 1].dist) - add_nearest(nearest, &found, n, node->index, cur_dist, node->co); + if (found < n || cur_dist < r_nearest[found - 1].dist) + add_nearest(r_nearest, &found, n, node->index, cur_dist, node->co); if (node->left) stack[cur++] = node->left; @@ -313,10 +345,10 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const floa else { cur_dist = cur_dist * cur_dist; - if (found < n || cur_dist < nearest[found - 1].dist) { + if (found < n || cur_dist < r_nearest[found - 1].dist) { cur_dist = squared_distance(node->co, co, node->nor, nor); - if (found < n || cur_dist < nearest[found - 1].dist) - add_nearest(nearest, &found, n, node->index, cur_dist, node->co); + if (found < n || cur_dist < r_nearest[found - 1].dist) + add_nearest(r_nearest, &found, n, node->index, cur_dist, node->co); if (node->right) stack[cur++] = node->right; @@ -325,17 +357,17 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const floa stack[cur++] = node->left; } if (UNLIKELY(cur + 3 > totstack)) { - stack = recalloc_nodes(stack, &totstack, defaultstack != stack); + stack = realloc_nodes(stack, &totstack, defaultstack != stack); } } for (i = 0; i < found; i++) - nearest[i].dist = sqrtf(nearest[i].dist); + r_nearest[i].dist = sqrtf(r_nearest[i].dist); if (stack != defaultstack) MEM_freeN(stack); - return found; + return (int)found; } static int range_compare(const void *a, const void *b) @@ -350,14 +382,13 @@ static int range_compare(const void *a, const void *b) else return 0; } -static void add_in_range(KDTreeNearest **ptn, int found, int *totfoundstack, int index, float dist, float *co) +static void add_in_range(KDTreeNearest **ptn, unsigned int found, unsigned int *totfoundstack, int index, float dist, float *co) { KDTreeNearest *to; if (found >= *totfoundstack) { KDTreeNearest *temp = MEM_mallocN((*totfoundstack + KD_FOUND_ALLOC_INC) * sizeof(KDTreeNode), "KDTree.treefoundstack"); memcpy(temp, *ptn, *totfoundstack * sizeof(KDTreeNearest)); - memset(temp + *totfoundstack, 0, sizeof(KDTreeNearest *) * KD_FOUND_ALLOC_INC); if (*ptn) MEM_freeN(*ptn); *ptn = temp; @@ -371,13 +402,19 @@ static void add_in_range(KDTreeNearest **ptn, int found, int *totfoundstack, int copy_v3_v3(to->co, co); } -int BLI_kdtree_range_search(KDTree *tree, float range, const float co[3], const float nor[3], KDTreeNearest **nearest) +/** + * Range search returns number of points found, with results in nearest + * Normal is optional, but if given will limit results to points in normal direction from co. + * Remember to free nearest after use! + */ +int BLI_kdtree_range_search(KDTree *tree, const float co[3], const float nor[3], + KDTreeNearest **r_nearest, float range) { KDTreeNode *root, *node = NULL; KDTreeNode **stack, *defaultstack[KD_STACK_INIT]; KDTreeNearest *foundstack = NULL; float range2 = range * range, dist2; - int totstack, cur = 0, found = 0, totfoundstack = 0; + unsigned int totstack, cur = 0, found = 0, totfoundstack = 0; if (!tree || !tree->root) return 0; @@ -429,7 +466,7 @@ int BLI_kdtree_range_search(KDTree *tree, float range, const float co[3], const } if (UNLIKELY(cur + 3 > totstack)) { - stack = recalloc_nodes(stack, &totstack, defaultstack != stack); + stack = realloc_nodes(stack, &totstack, defaultstack != stack); } } @@ -439,7 +476,7 @@ int BLI_kdtree_range_search(KDTree *tree, float range, const float co[3], const if (found) qsort(foundstack, found, sizeof(KDTreeNearest), range_compare); - *nearest = foundstack; + *r_nearest = foundstack; - return found; + return (int)found; } diff --git a/source/blender/editors/physics/particle_edit.c b/source/blender/editors/physics/particle_edit.c index dc7ec16d7c1..1a561efd217 100644 --- a/source/blender/editors/physics/particle_edit.c +++ b/source/blender/editors/physics/particle_edit.c @@ -2453,7 +2453,7 @@ static int remove_doubles_exec(bContext *C, wmOperator *op) copy_v3_v3(co, point->keys->co); mul_m4_v3(mat, co); - totn= BLI_kdtree_find_n_nearest(tree, 10, co, NULL, nearest); + totn = BLI_kdtree_find_nearest_n(tree, co, NULL, nearest, 10); for (n=0; n<totn; n++) { /* this needs a custom threshold still */ @@ -3459,7 +3459,7 @@ static int brush_add(PEData *data, short number) float maxd, totw=0.0, weight[3]; psys_particle_on_dm(psmd->dm, psys->part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, co1, 0, 0, 0, 0, 0); - maxw= BLI_kdtree_find_n_nearest(tree, 3, co1, NULL, ptn); + maxw = BLI_kdtree_find_nearest_n(tree, co1, NULL, ptn, 3); maxd= ptn[maxw-1].dist; |