diff options
30 files changed, 236 insertions, 232 deletions
diff --git a/source/blender/blenkernel/BKE_object.h b/source/blender/blenkernel/BKE_object.h index 9e6366f9992..4a1470797ba 100644 --- a/source/blender/blenkernel/BKE_object.h +++ b/source/blender/blenkernel/BKE_object.h @@ -339,7 +339,7 @@ struct LinkNode *BKE_object_relational_superset( struct LinkNode *BKE_object_groups(struct Main *bmain, struct Scene *scene, struct Object *ob); void BKE_object_groups_clear(struct Main *bmain, struct Scene *scene, struct Object *object); -struct KDTree *BKE_object_as_kdtree(struct Object *ob, int *r_tot); +struct KDTree_3d *BKE_object_as_kdtree(struct Object *ob, int *r_tot); bool BKE_object_modifier_use_time(struct Object *ob, struct ModifierData *md); diff --git a/source/blender/blenkernel/BKE_particle.h b/source/blender/blenkernel/BKE_particle.h index 56f64829eb1..b2b7f9f9cb5 100644 --- a/source/blender/blenkernel/BKE_particle.h +++ b/source/blender/blenkernel/BKE_particle.h @@ -45,7 +45,7 @@ struct CustomData_MeshMasks; struct Depsgraph; struct Depsgraph; struct EdgeHash; -struct KDTree; +struct KDTree_3d; struct LatticeDeformData; struct LinkNode; struct MCol; @@ -136,7 +136,7 @@ typedef struct ParticleThreadContext { struct Material *ma; /* distribution */ - struct KDTree *tree; + struct KDTree_3d *tree; struct ParticleSeam *seams; int totseam; diff --git a/source/blender/blenkernel/BKE_pointcache.h b/source/blender/blenkernel/BKE_pointcache.h index 6f0145a493d..9cfc43b2e5b 100644 --- a/source/blender/blenkernel/BKE_pointcache.h +++ b/source/blender/blenkernel/BKE_pointcache.h @@ -226,7 +226,7 @@ typedef struct PTCacheUndo { /* particles stuff */ struct ParticleData *particles; - struct KDTree *emitter_field; + struct KDTree_3d *emitter_field; float *emitter_cosnos; int psys_flag; @@ -257,7 +257,7 @@ typedef struct PTCacheEdit { struct ParticleSystem *psys_eval; struct ParticleSystemModifierData *psmd; struct ParticleSystemModifierData *psmd_eval; - struct KDTree *emitter_field; + struct KDTree_3d *emitter_field; float *emitter_cosnos; /* localspace face centers and normals (average of its verts), from the derived mesh */ int *mirror_cache; diff --git a/source/blender/blenkernel/intern/boids.c b/source/blender/blenkernel/intern/boids.c index 8b71aa0fb69..c092b2c7e79 100644 --- a/source/blender/blenkernel/intern/boids.c +++ b/source/blender/blenkernel/intern/boids.c @@ -206,7 +206,7 @@ static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues * { const int raycast_flag = BVH_RAYCAST_DEFAULT & ~(BVH_RAYCAST_WATERTIGHT); BoidRuleAvoidCollision *acbr = (BoidRuleAvoidCollision*) rule; - KDTreeNearest *ptn = NULL; + KDTreeNearest_3d *ptn = NULL; ParticleTarget *pt; BoidParticle *bpa = pa->boid; ColliderCache *coll; @@ -274,7 +274,7 @@ 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_with_len_squared_cb( + neighbors = BLI_kdtree_3d_range_search_with_len_squared_cb( bbd->sim->psys->tree, pa->prev_state.co, &ptn, acbr->look_ahead * len_v3(pa->prev_state.vel), len_squared_v3v3_with_normal_bias, pa->prev_state.ave); if (neighbors > 1) for (n=1; n<neighbors; n++) { @@ -323,7 +323,7 @@ static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues * if (epsys) { BLI_assert(epsys->tree != NULL); - neighbors = BLI_kdtree_range_search_with_len_squared_cb( + neighbors = BLI_kdtree_3d_range_search_with_len_squared_cb( epsys->tree, pa->prev_state.co, &ptn, acbr->look_ahead * len_v3(pa->prev_state.vel), len_squared_v3v3_with_normal_bias, pa->prev_state.ave); @@ -377,11 +377,11 @@ static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues * } static int rule_separate(BoidRule *UNUSED(rule), BoidBrainData *bbd, BoidValues *val, ParticleData *pa) { - KDTreeNearest *ptn = NULL; + KDTreeNearest_3d *ptn = NULL; 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( + int neighbors = BLI_kdtree_3d_range_search( bbd->sim->psys->tree, pa->prev_state.co, &ptn, 2.0f * val->personal_space * pa->size); int ret = 0; @@ -401,7 +401,7 @@ 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( + neighbors = BLI_kdtree_3d_range_search( epsys->tree, pa->prev_state.co, &ptn, 2.0f * val->personal_space * pa->size); @@ -421,9 +421,9 @@ static int rule_separate(BoidRule *UNUSED(rule), BoidBrainData *bbd, BoidValues } static int rule_flock(BoidRule *UNUSED(rule), BoidBrainData *bbd, BoidValues *UNUSED(val), ParticleData *pa) { - KDTreeNearest ptn[11]; + KDTreeNearest_3d ptn[11]; float vec[3] = {0.0f, 0.0f, 0.0f}, loc[3] = {0.0f, 0.0f, 0.0f}; - int neighbors = BLI_kdtree_find_nearest_n_with_len_squared_cb( + int neighbors = BLI_kdtree_3d_find_nearest_n_with_len_squared_cb( bbd->sim->psys->tree, pa->state.co, ptn, ARRAY_SIZE(ptn), len_squared_v3v3_with_normal_bias, pa->prev_state.ave); int n; @@ -639,7 +639,7 @@ static int rule_average_speed(BoidRule *rule, BoidBrainData *bbd, BoidValues *va static int rule_fight(BoidRule *rule, BoidBrainData *bbd, BoidValues *val, ParticleData *pa) { BoidRuleFight *fbr = (BoidRuleFight*)rule; - KDTreeNearest *ptn = NULL; + KDTreeNearest_3d *ptn = NULL; ParticleTarget *pt; ParticleData *epars; ParticleData *enemy_pa = NULL; @@ -652,7 +652,7 @@ 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( + int neighbors = BLI_kdtree_3d_range_search( bbd->sim->psys->tree, pa->prev_state.co, &ptn, fbr->distance); for (n=0; n<neighbors; n++) { @@ -670,7 +670,7 @@ static int rule_fight(BoidRule *rule, BoidBrainData *bbd, BoidValues *val, Parti if (epsys) { epars = epsys->particles; - neighbors = BLI_kdtree_range_search( + neighbors = BLI_kdtree_3d_range_search( epsys->tree, pa->prev_state.co, &ptn, fbr->distance); diff --git a/source/blender/blenkernel/intern/dynamicpaint.c b/source/blender/blenkernel/intern/dynamicpaint.c index eeaf0710a5f..0419a5ac348 100644 --- a/source/blender/blenkernel/intern/dynamicpaint.c +++ b/source/blender/blenkernel/intern/dynamicpaint.c @@ -4237,7 +4237,7 @@ static void dynamic_paint_paint_particle_cell_point_cb_ex( const float timescale = data->timescale; const int c_index = data->c_index; - KDTree *tree = data->treeData; + KDTree_3d *tree = data->treeData; const float solidradius = data->solidradius; const float smooth = brush->particle_smooth * surface->radius_scale; @@ -4255,11 +4255,11 @@ static void dynamic_paint_paint_particle_cell_point_cb_ex( * It's enough to just find the nearest one. */ { - KDTreeNearest nearest; + KDTreeNearest_3d nearest; float smooth_range, part_solidradius; /* Find nearest particle and get distance to it */ - BLI_kdtree_find_nearest(tree, bData->realCoord[bData->s_pos[index]].v, &nearest); + BLI_kdtree_3d_find_nearest(tree, bData->realCoord[bData->s_pos[index]].v, &nearest); /* if outside maximum range, no other particle can influence either */ if (nearest.dist > range) return; @@ -4291,7 +4291,7 @@ static void dynamic_paint_paint_particle_cell_point_cb_ex( * If we use per particle radius, we have to sample all particles * within max radius range */ - KDTreeNearest *nearest; + KDTreeNearest_3d *nearest; float smooth_range = smooth * (1.0f - strength), dist; /* calculate max range that can have particles with higher influence than the nearest one */ @@ -4299,7 +4299,7 @@ static void dynamic_paint_paint_particle_cell_point_cb_ex( /* Make gcc happy! */ dist = max_range; - const int particles = BLI_kdtree_range_search( + const int particles = BLI_kdtree_3d_range_search( tree, bData->realCoord[bData->s_pos[index]].v, &nearest, max_range); /* Find particle that produces highest influence */ @@ -4397,7 +4397,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface, PaintBakeData *bData = sData->bData; VolumeGrid *grid = bData->grid; - KDTree *tree; + KDTree_3d *tree; int particlesAdded = 0; int invalidParticles = 0; int p = 0; @@ -4416,7 +4416,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface, /* * Build a kd-tree to optimize distance search */ - tree = BLI_kdtree_new(psys->totpart); + tree = BLI_kdtree_3d_new(psys->totpart); /* loop through particles and insert valid ones to the tree */ p = 0; @@ -4440,7 +4440,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface, if (!boundIntersectPoint(&grid->grid_bounds, pa->state.co, range)) continue; - BLI_kdtree_insert(tree, p, pa->state.co); + BLI_kdtree_3d_insert(tree, p, pa->state.co); /* calc particle system bounds */ boundInsert(&part_bb, pa->state.co); @@ -4452,7 +4452,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface, /* If no suitable particles were found, exit */ if (particlesAdded < 1) { - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); return 1; } @@ -4465,7 +4465,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface, int total_cells = grid->dim[0] * grid->dim[1] * grid->dim[2]; /* balance tree */ - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); /* loop through space partitioning grid */ for (c_index = 0; c_index < total_cells; c_index++) { @@ -4493,7 +4493,7 @@ static int dynamicPaint_paintParticles(DynamicPaintSurface *surface, } } BLI_threaded_malloc_end(); - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); return 1; } diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c index 66b888c84f2..4f8be846b37 100644 --- a/source/blender/blenkernel/intern/object.c +++ b/source/blender/blenkernel/intern/object.c @@ -3968,7 +3968,7 @@ void BKE_object_groups_clear(Main *bmain, Scene *scene, Object *ob) } /** - * Return a KDTree from the deformed object (in worldspace) + * Return a KDTree_3d from the deformed object (in worldspace) * * \note Only mesh objects currently support deforming, others are TODO. * @@ -3976,9 +3976,9 @@ void BKE_object_groups_clear(Main *bmain, Scene *scene, Object *ob) * \param r_tot: * \return The kdtree or NULL if it can't be created. */ -KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot) +KDTree_3d *BKE_object_as_kdtree(Object *ob, int *r_tot) { - KDTree *tree = NULL; + KDTree_3d *tree = NULL; unsigned int tot = 0; switch (ob->type) { @@ -3996,14 +3996,14 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot) /* tree over-allocs in case where some verts have ORIGINDEX_NONE */ tot = 0; - tree = BLI_kdtree_new(totvert); + tree = BLI_kdtree_3d_new(totvert); /* we don't how how many verts from the DM we can use */ for (i = 0; i < totvert; i++) { if (index[i] != ORIGINDEX_NONE) { float co[3]; mul_v3_m4v3(co, ob->obmat, mvert[i].co); - BLI_kdtree_insert(tree, index[i], co); + BLI_kdtree_3d_insert(tree, index[i], co); tot++; } } @@ -4012,16 +4012,16 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot) MVert *mvert = me->mvert; tot = me->totvert; - tree = BLI_kdtree_new(tot); + tree = BLI_kdtree_3d_new(tot); for (i = 0; i < tot; i++) { float co[3]; mul_v3_m4v3(co, ob->obmat, mvert[i].co); - BLI_kdtree_insert(tree, i, co); + BLI_kdtree_3d_insert(tree, i, co); } } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); break; } case OB_CURVE: @@ -4034,7 +4034,7 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot) Nurb *nu; tot = BKE_nurbList_verts_count_without_handles(&cu->nurb); - tree = BLI_kdtree_new(tot); + tree = BLI_kdtree_3d_new(tot); i = 0; nu = cu->nurb.first; @@ -4047,7 +4047,7 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot) while (a--) { float co[3]; mul_v3_m4v3(co, ob->obmat, bezt->vec[1]); - BLI_kdtree_insert(tree, i++, co); + BLI_kdtree_3d_insert(tree, i++, co); bezt++; } } @@ -4059,14 +4059,14 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot) while (a--) { float co[3]; mul_v3_m4v3(co, ob->obmat, bp->vec); - BLI_kdtree_insert(tree, i++, co); + BLI_kdtree_3d_insert(tree, i++, co); bp++; } } nu = nu->next; } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); break; } case OB_LATTICE: @@ -4077,16 +4077,16 @@ KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot) unsigned int i; tot = lt->pntsu * lt->pntsv * lt->pntsw; - tree = BLI_kdtree_new(tot); + tree = BLI_kdtree_3d_new(tot); i = 0; for (bp = lt->def; i < tot; bp++) { float co[3]; mul_v3_m4v3(co, ob->obmat, bp->vec); - BLI_kdtree_insert(tree, i++, co); + BLI_kdtree_3d_insert(tree, i++, co); } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); break; } } diff --git a/source/blender/blenkernel/intern/particle.c b/source/blender/blenkernel/intern/particle.c index bdf0b239917..4abc57ca1c9 100644 --- a/source/blender/blenkernel/intern/particle.c +++ b/source/blender/blenkernel/intern/particle.c @@ -650,7 +650,7 @@ void psys_free(Object *ob, ParticleSystem *psys) BLI_freelistN(&psys->targets); BLI_bvhtree_free(psys->bvhtree); - BLI_kdtree_free(psys->tree); + BLI_kdtree_3d_free(psys->tree); if (psys->fluid_springs) MEM_freeN(psys->fluid_springs); @@ -1920,7 +1920,7 @@ void psys_find_parents(ParticleSimulationData *sim, const bool use_render_params { ParticleSystem *psys = sim->psys; ParticleSettings *part = sim->psys->part; - KDTree *tree; + KDTree_3d *tree; ChildParticle *cpa; ParticleTexture ptex; int p, totparent, totchild = sim->psys->totchild; @@ -1936,7 +1936,7 @@ void psys_find_parents(ParticleSimulationData *sim, const bool use_render_params totparent = sim->psys->totpart; } - tree = BLI_kdtree_new(totparent); + tree = BLI_kdtree_3d_new(totparent); for (p = 0, cpa = sim->psys->child; p < totparent; p++, cpa++) { psys_particle_on_emitter(sim->psmd, from, cpa->num, DMCACHE_ISCHILD, cpa->fuv, cpa->foffset, co, 0, 0, 0, orco); @@ -1945,18 +1945,18 @@ void psys_find_parents(ParticleSimulationData *sim, const bool use_render_params get_cpa_texture(sim->psmd->mesh_final, psys, part, psys->particles + cpa->pa[0], p, cpa->num, cpa->fuv, orco, &ptex, PAMAP_DENS | PAMAP_CHILD, psys->cfra); if (ptex.exist >= psys_frand(psys, p + 24)) { - BLI_kdtree_insert(tree, p, orco); + BLI_kdtree_3d_insert(tree, p, orco); } } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); for (; p < totchild; p++, cpa++) { psys_particle_on_emitter(sim->psmd, from, cpa->num, DMCACHE_ISCHILD, cpa->fuv, cpa->foffset, co, 0, 0, 0, orco); - cpa->parent = BLI_kdtree_find_nearest(tree, orco, NULL); + cpa->parent = BLI_kdtree_3d_find_nearest(tree, orco, NULL); } - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); } static bool psys_thread_context_init_path( diff --git a/source/blender/blenkernel/intern/particle_distribute.c b/source/blender/blenkernel/intern/particle_distribute.c index 4485afb09de..bbf8fece5ff 100644 --- a/source/blender/blenkernel/intern/particle_distribute.c +++ b/source/blender/blenkernel/intern/particle_distribute.c @@ -464,12 +464,12 @@ static void distribute_from_verts_exec(ParticleTask *thread, ParticleData *pa, i #if ONLY_WORKING_WITH_PA_VERTS if (ctx->tree) { - KDTreeNearest ptn[3]; + KDTreeNearest_3d ptn[3]; int w, maxw; psys_particle_on_dm(ctx->mesh,from,pa->num,pa->num_dmcache,pa->fuv,pa->foffset,co1,0,0,0,orco1,0); BKE_mesh_orco_verts_transform(ob->data, &orco1, 1, 1); - maxw = BLI_kdtree_find_nearest_n(ctx->tree,orco1,ptn,3); + maxw = BLI_kdtree_3d_find_nearest_n(ctx->tree,orco1,ptn,3); for (w=0; w<maxw; w++) { pa->verts[w]=ptn->num; @@ -654,7 +654,7 @@ static void distribute_children_exec(ParticleTask *thread, ChildParticle *cpa, i cpa->num = ctx->index[p]; if (ctx->tree) { - KDTreeNearest ptn[10]; + KDTreeNearest_3d ptn[10]; int w,maxw;//, do_seams; float maxd /*, mind,dd */, totw= 0.0f; int parent[10]; @@ -662,7 +662,7 @@ static void distribute_children_exec(ParticleTask *thread, ChildParticle *cpa, i psys_particle_on_dm(mesh,cfrom,cpa->num,DMCACHE_ISCHILD,cpa->fuv,cpa->foffset,co1,nor1,NULL,NULL,orco1); BKE_mesh_orco_verts_transform(ob->data, &orco1, 1, 1); - maxw = BLI_kdtree_find_nearest_n(ctx->tree,orco1,ptn,3); + maxw = BLI_kdtree_3d_find_nearest_n(ctx->tree,orco1,ptn,3); maxd=ptn[maxw-1].dist; /* mind=ptn[0].dist; */ /* UNUSED */ @@ -809,7 +809,7 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti ParticleData *pa=0, *tpars= 0; ParticleSettings *part; ParticleSeam *seams= 0; - KDTree *tree=0; + KDTree_3d *tree=0; Mesh *mesh = NULL; float *jit= NULL; int i, p=0; @@ -883,15 +883,15 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti children=1; - tree=BLI_kdtree_new(totpart); + tree=BLI_kdtree_3d_new(totpart); for (p=0,pa=psys->particles; p<totpart; p++,pa++) { psys_particle_on_dm(mesh,part->from,pa->num,pa->num_dmcache,pa->fuv,pa->foffset,co,nor,0,0,orco); BKE_mesh_orco_verts_transform(ob->data, &orco, 1, 1); - BLI_kdtree_insert(tree, p, orco); + BLI_kdtree_3d_insert(tree, p, orco); } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); totpart = psys_get_tot_child(scene, psys, use_render_params); cfrom = from = PART_FROM_FACE; @@ -917,7 +917,7 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti float (*orcodata)[3] = CustomData_get_layer(&mesh->vdata, CD_ORCO); int totvert = mesh->totvert; - tree=BLI_kdtree_new(totvert); + tree=BLI_kdtree_3d_new(totvert); for (p=0; p<totvert; p++) { if (orcodata) { @@ -926,10 +926,10 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti } else copy_v3_v3(co,mv[p].co); - BLI_kdtree_insert(tree, p, co); + BLI_kdtree_3d_insert(tree, p, co); } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); } } @@ -944,7 +944,7 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti if (mesh != final_mesh) BKE_id_free(NULL, mesh); - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); BLI_rng_free(rng); return 0; diff --git a/source/blender/blenkernel/intern/particle_system.c b/source/blender/blenkernel/intern/particle_system.c index 2975eaaf5fc..28a2e6e94cb 100644 --- a/source/blender/blenkernel/intern/particle_system.c +++ b/source/blender/blenkernel/intern/particle_system.c @@ -512,7 +512,7 @@ void psys_thread_context_free(ParticleThreadContext *ctx) if (ctx->index) MEM_freeN(ctx->index); if (ctx->seams) MEM_freeN(ctx->seams); //if (ctx->vertpart) MEM_freeN(ctx->vertpart); - BLI_kdtree_free(ctx->tree); + BLI_kdtree_3d_free(ctx->tree); if (ctx->clumpcurve != NULL) { curvemapping_free(ctx->clumpcurve); @@ -1280,18 +1280,18 @@ void psys_update_particle_tree(ParticleSystem *psys, float cfra) totpart++; } - BLI_kdtree_free(psys->tree); - psys->tree = BLI_kdtree_new(psys->totpart); + BLI_kdtree_3d_free(psys->tree); + psys->tree = BLI_kdtree_3d_new(psys->totpart); LOOP_SHOWN_PARTICLES { if (pa->alive == PARS_ALIVE) { if (pa->state.time == cfra) - BLI_kdtree_insert(psys->tree, p, pa->prev_state.co); + BLI_kdtree_3d_insert(psys->tree, p, pa->prev_state.co); else - BLI_kdtree_insert(psys->tree, p, pa->state.co); + BLI_kdtree_3d_insert(psys->tree, p, pa->state.co); } } - BLI_kdtree_balance(psys->tree); + BLI_kdtree_3d_balance(psys->tree); psys->tree_frame = cfra; } diff --git a/source/blender/blenkernel/intern/smoke.c b/source/blender/blenkernel/intern/smoke.c index 4b9dd9ac6e3..82acc272c6b 100644 --- a/source/blender/blenkernel/intern/smoke.c +++ b/source/blender/blenkernel/intern/smoke.c @@ -1200,7 +1200,7 @@ static void em_combineMaps(EmissionMap *output, EmissionMap *em2, int hires_mult typedef struct EmitFromParticlesData { SmokeFlowSettings *sfs; - KDTree *tree; + KDTree_3d *tree; int hires_multiplier; EmissionMap *em; @@ -1237,9 +1237,9 @@ static void emit_from_particles_task_cb( const float ray_start[3] = {((float)lx) + 0.5f, ((float)ly) + 0.5f, ((float)lz) + 0.5f}; /* find particle distance from the kdtree */ - KDTreeNearest nearest; + KDTreeNearest_3d nearest; const float range = data->solid + data->smooth; - BLI_kdtree_find_nearest(data->tree, ray_start, &nearest); + BLI_kdtree_3d_find_nearest(data->tree, ray_start, &nearest); if (nearest.dist < range) { em->influence[index] = (nearest.dist < data->solid) ? @@ -1263,9 +1263,9 @@ static void emit_from_particles_task_cb( const float ray_start[3] = {lx + 0.5f * data->hr, ly + 0.5f * data->hr, lz + 0.5f * data->hr}; /* find particle distance from the kdtree */ - KDTreeNearest nearest; + KDTreeNearest_3d nearest; const float range = data->solid + data->hr_smooth; - BLI_kdtree_find_nearest(data->tree, ray_start, &nearest); + BLI_kdtree_3d_find_nearest(data->tree, ray_start, &nearest); if (nearest.dist < range) { em->influence_high[index] = (nearest.dist < data->solid) ? @@ -1295,7 +1295,7 @@ static void emit_from_particles( const float solid = sfs->particle_size * 0.5f; const float smooth = 0.5f; /* add 0.5 cells of linear falloff to reduce aliasing */ int hires_multiplier = 1; - KDTree *tree = NULL; + KDTree_3d *tree = NULL; sim.depsgraph = depsgraph; sim.scene = scene; @@ -1325,7 +1325,7 @@ static void emit_from_particles( /* setup particle radius emission if enabled */ if (sfs->flags & MOD_SMOKE_FLOW_USE_PART_SIZE) { - tree = BLI_kdtree_new(psys->totpart + psys->totchild); + tree = BLI_kdtree_3d_new(psys->totpart + psys->totchild); /* check need for high resolution map */ if ((sds->flags & MOD_SMOKE_HIGHRES) && (sds->highres_sampling == SM_HRES_FULLSAMPLE)) { @@ -1365,7 +1365,7 @@ static void emit_from_particles( mul_mat3_m4_v3(sds->imat, &particle_vel[valid_particles * 3]); if (sfs->flags & MOD_SMOKE_FLOW_USE_PART_SIZE) { - BLI_kdtree_insert(tree, valid_particles, pos); + BLI_kdtree_3d_insert(tree, valid_particles, pos); } /* calculate emission map bounds */ @@ -1423,7 +1423,7 @@ static void emit_from_particles( res[i] = em->res[i] * hires_multiplier; } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); EmitFromParticlesData data = { .sfs = sfs, .tree = tree, .hires_multiplier = hires_multiplier, .hr = hr, @@ -1441,7 +1441,7 @@ static void emit_from_particles( } if (sfs->flags & MOD_SMOKE_FLOW_USE_PART_SIZE) { - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); } /* free data */ diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/BLI_kdtree.h index eb0421eaec1..af10a448423 100644 --- a/source/blender/blenlib/BLI_kdtree.h +++ b/source/blender/blenlib/BLI_kdtree.h @@ -24,9 +24,13 @@ /* 3D version */ #define KD_DIMS 3 -#define KDTREE_PREFIX_ID BLI_kdtree +#define KDTREE_PREFIX_ID BLI_kdtree_3d +#define KDTree KDTree_3d +#define KDTreeNearest KDTreeNearest_3d #include "BLI_kdtree_impl.h" #undef KD_DIMS +#undef KDTree +#undef KDTreeNearest #undef KDTREE_PREFIX_ID /* 4D version */ diff --git a/source/blender/blenlib/intern/kdtree_3d.c b/source/blender/blenlib/intern/kdtree_3d.c index 1da93772aa9..2f85755b676 100644 --- a/source/blender/blenlib/intern/kdtree_3d.c +++ b/source/blender/blenlib/intern/kdtree_3d.c @@ -19,7 +19,7 @@ */ #define KD_DIMS 3 -#define KDTREE_PREFIX_ID BLI_kdtree +#define KDTREE_PREFIX_ID BLI_kdtree_3d +#define KDTree KDTree_3d +#define KDTreeNearest KDTreeNearest_3d # include "kdtree_impl.h" -#undef DIMS -#undef KDTREE_PREFIX_ID diff --git a/source/blender/blenlib/intern/kdtree_impl.h b/source/blender/blenlib/intern/kdtree_impl.h index 2d4a657ae81..62bd51eea80 100644 --- a/source/blender/blenlib/intern/kdtree_impl.h +++ b/source/blender/blenlib/intern/kdtree_impl.h @@ -325,7 +325,7 @@ int BLI_kdtree_nd_(find_nearest)( /** - * A version of #BLI_kdtree_find_nearest which runs a callback + * A version of #BLI_kdtree_3d_find_nearest which runs a callback * to filter out values. * * \param filter_cb: Filter find results, @@ -711,7 +711,7 @@ int BLI_kdtree_nd_(range_search)( } /** - * A version of #BLI_kdtree_range_search which runs a callback + * A version of #BLI_kdtree_3d_range_search which runs a callback * instead of allocating an array. * * \param search_cb: Called for every node found in \a range, false return value performs an early exit. @@ -796,7 +796,7 @@ static uint *kdtree_order(const KDTree *tree) } /* -------------------------------------------------------------------- */ -/** \name BLI_kdtree_calc_duplicates_fast +/** \name BLI_kdtree_3d_calc_duplicates_fast * \{ */ struct DeDuplicateParams { diff --git a/source/blender/bmesh/operators/bmo_removedoubles.c b/source/blender/bmesh/operators/bmo_removedoubles.c index 1432e15185e..eba8c37f1e0 100644 --- a/source/blender/bmesh/operators/bmo_removedoubles.c +++ b/source/blender/bmesh/operators/bmo_removedoubles.c @@ -634,9 +634,9 @@ static void bmesh_find_doubles_common( int *duplicates = MEM_mallocN(sizeof(int) * verts_len, __func__); { - KDTree *tree = BLI_kdtree_new(verts_len); + KDTree_3d *tree = BLI_kdtree_3d_new(verts_len); for (int i = 0; i < verts_len; i++) { - BLI_kdtree_insert(tree, i, verts[i]->co); + BLI_kdtree_3d_insert(tree, i, verts[i]->co); if (has_keep_vert && BMO_vert_flag_test(bm, verts[i], VERT_KEEP)) { duplicates[i] = i; } @@ -645,9 +645,9 @@ static void bmesh_find_doubles_common( } } - BLI_kdtree_balance(tree); - found_duplicates = BLI_kdtree_calc_duplicates_fast(tree, dist, false, duplicates) != 0; - BLI_kdtree_free(tree); + BLI_kdtree_3d_balance(tree); + found_duplicates = BLI_kdtree_3d_calc_duplicates_fast(tree, dist, false, duplicates) != 0; + BLI_kdtree_3d_free(tree); } if (found_duplicates) { diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c b/source/blender/bmesh/tools/bmesh_decimate_collapse.c index 7f6bcf12f84..e5dd6491076 100644 --- a/source/blender/bmesh/tools/bmesh_decimate_collapse.c +++ b/source/blender/bmesh/tools/bmesh_decimate_collapse.c @@ -424,9 +424,9 @@ static int *bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit) uint i; int *edge_symmetry_map; const float limit_sq = SQUARE(limit); - KDTree *tree; + KDTree_3d *tree; - tree = BLI_kdtree_new(bm->totedge); + tree = BLI_kdtree_3d_new(bm->totedge); etable = MEM_mallocN(sizeof(*etable) * bm->totedge, __func__); edge_symmetry_map = MEM_mallocN(sizeof(*edge_symmetry_map) * bm->totedge, __func__); @@ -434,12 +434,12 @@ static int *bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit) BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) { float co[3]; mid_v3_v3v3(co, e->v1->co, e->v2->co); - BLI_kdtree_insert(tree, i, co); + BLI_kdtree_3d_insert(tree, i, co); etable[i] = e; edge_symmetry_map[i] = -1; } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); sym_data.etable = etable; sym_data.limit_sq = limit_sq; @@ -457,7 +457,7 @@ static int *bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit) sub_v3_v3v3(sym_data.e_dir, sym_data.e_v2_co, sym_data.e_v1_co); sym_data.e_found_index = -1; - BLI_kdtree_range_search_cb(tree, co, limit, bm_edge_symmetry_check_cb, &sym_data); + BLI_kdtree_3d_range_search_cb(tree, co, limit, bm_edge_symmetry_check_cb, &sym_data); if (sym_data.e_found_index != -1) { const int i_other = sym_data.e_found_index; @@ -468,7 +468,7 @@ static int *bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit) } MEM_freeN(etable); - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); return edge_symmetry_map; } diff --git a/source/blender/editors/curve/editcurve_select.c b/source/blender/editors/curve/editcurve_select.c index 25470f7344a..ba9a42a6c2b 100644 --- a/source/blender/editors/curve/editcurve_select.c +++ b/source/blender/editors/curve/editcurve_select.c @@ -1362,7 +1362,7 @@ static void nurb_bpoint_direction_worldspace_get(Object *ob, Nurb *nu, BPoint *b normalize_v3(r_dir); } -static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, KDTree *r_tree) +static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, KDTree_3d *r_tree) { float tree_entry[3] = {0.0f, 0.0f, 0.0f}; @@ -1393,7 +1393,7 @@ static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, K break; } } - BLI_kdtree_insert(r_tree, tree_index++, tree_entry); + BLI_kdtree_3d_insert(r_tree, tree_index++, tree_entry); } } } @@ -1423,7 +1423,7 @@ static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, K break; } } - BLI_kdtree_insert(r_tree, tree_index++, tree_entry); + BLI_kdtree_3d_insert(r_tree, tree_index++, tree_entry); } } } @@ -1431,7 +1431,7 @@ static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, K static bool curve_nurb_select_similar_type( Object *ob, Nurb *nu, const int type, - const KDTree *tree, const float thresh, const int compare) + const KDTree_3d *tree, const float thresh, const int compare) { const float thresh_cos = cosf(thresh * (float)M_PI_2); bool changed = false; @@ -1465,8 +1465,8 @@ static bool curve_nurb_select_similar_type( { float dir[3]; nurb_bezt_direction_worldspace_get(ob, nu, bezt, dir); - KDTreeNearest nearest; - if (BLI_kdtree_find_nearest(tree, dir, &nearest) != -1) { + KDTreeNearest_3d nearest; + if (BLI_kdtree_3d_find_nearest(tree, dir, &nearest) != -1) { float orient = angle_normalized_v3v3(dir, nearest.co); float delta = thresh_cos - fabsf(cosf(orient)); if (ED_select_similar_compare_float(delta, thresh, compare)) { @@ -1513,8 +1513,8 @@ static bool curve_nurb_select_similar_type( { float dir[3]; nurb_bpoint_direction_worldspace_get(ob, nu, bp, dir); - KDTreeNearest nearest; - if (BLI_kdtree_find_nearest(tree, dir, &nearest) != -1) { + KDTreeNearest_3d nearest; + if (BLI_kdtree_3d_find_nearest(tree, dir, &nearest) != -1) { float orient = angle_normalized_v3v3(dir, nearest.co); float delta = fabsf(cosf(orient)) - thresh_cos; if (ED_select_similar_compare_float(delta, thresh, compare)) { @@ -1560,14 +1560,14 @@ static int curve_select_similar_exec(bContext *C, wmOperator *op) return OPERATOR_CANCELLED; } - KDTree *tree = NULL; + KDTree_3d *tree = NULL; short type_ref = 0; switch (optype) { case SIMCURHAND_RADIUS: case SIMCURHAND_WEIGHT: case SIMCURHAND_DIRECTION: - tree = BLI_kdtree_new(tot_nurbs_selected_all); + tree = BLI_kdtree_3d_new(tot_nurbs_selected_all); break; } @@ -1598,7 +1598,7 @@ static int curve_select_similar_exec(bContext *C, wmOperator *op) } if (tree != NULL) { - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); } /* Select control points with desired type. */ @@ -1635,7 +1635,7 @@ static int curve_select_similar_exec(bContext *C, wmOperator *op) MEM_freeN(objects); if (tree != NULL) { - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); } return OPERATOR_FINISHED; diff --git a/source/blender/editors/include/ED_select_utils.h b/source/blender/editors/include/ED_select_utils.h index a7b9ac7e6c9..87045be9932 100644 --- a/source/blender/editors/include/ED_select_utils.h +++ b/source/blender/editors/include/ED_select_utils.h @@ -21,7 +21,7 @@ #ifndef __ED_SELECT_UTILS_H__ #define __ED_SELECT_UTILS_H__ -struct KDTree; +struct KDTree_3d; enum { SEL_TOGGLE = 0, @@ -55,7 +55,7 @@ int ED_select_op_action(const eSelectOp sel_op, const bool is_select, const bool int ED_select_op_action_deselected(const eSelectOp sel_op, const bool is_select, const bool is_inside); int ED_select_similar_compare_float(const float delta, const float thresh, const int compare); -bool ED_select_similar_compare_float_tree(const struct KDTree *tree, const float length, const float thresh, const int compare); +bool ED_select_similar_compare_float_tree(const struct KDTree_3d *tree, const float length, const float thresh, const int compare); eSelectOp ED_select_op_modal(const eSelectOp sel_op, const bool is_first); diff --git a/source/blender/editors/mesh/editmesh_select_similar.c b/source/blender/editors/mesh/editmesh_select_similar.c index 299db63eca3..59c34578777 100644 --- a/source/blender/editors/mesh/editmesh_select_similar.c +++ b/source/blender/editors/mesh/editmesh_select_similar.c @@ -183,7 +183,7 @@ static int similar_face_select_exec(bContext *C, wmOperator *op) return OPERATOR_CANCELLED; } - KDTree *tree = NULL; + KDTree_3d *tree = NULL; KDTree_4d *tree_plane = NULL; GSet *gset = NULL; GSet **gset_array = NULL; @@ -193,7 +193,7 @@ static int similar_face_select_exec(bContext *C, wmOperator *op) case SIMFACE_AREA: case SIMFACE_PERIMETER: case SIMFACE_NORMAL: - tree = BLI_kdtree_new(tot_faces_selected_all); + tree = BLI_kdtree_3d_new(tot_faces_selected_all); break; case SIMFACE_COPLANAR: tree_plane = BLI_kdtree_4d_new(tot_faces_selected_all); @@ -273,14 +273,14 @@ static int similar_face_select_exec(bContext *C, wmOperator *op) { float area = BM_face_calc_area_with_mat3(face, ob_m3); float dummy[3] = {area, 0.0f, 0.0f}; - BLI_kdtree_insert(tree, tree_index++, dummy); + BLI_kdtree_3d_insert(tree, tree_index++, dummy); break; } case SIMFACE_PERIMETER: { float perimeter = BM_face_calc_perimeter_with_mat3(face, ob_m3); float dummy[3] = {perimeter, 0.0f, 0.0f}; - BLI_kdtree_insert(tree, tree_index++, dummy); + BLI_kdtree_3d_insert(tree, tree_index++, dummy); break; } case SIMFACE_NORMAL: @@ -290,7 +290,7 @@ static int similar_face_select_exec(bContext *C, wmOperator *op) mul_transposed_mat3_m4_v3(ob->imat, normal); normalize_v3(normal); - BLI_kdtree_insert(tree, tree_index++, normal); + BLI_kdtree_3d_insert(tree, tree_index++, normal); break; } case SIMFACE_COPLANAR: @@ -337,7 +337,7 @@ static int similar_face_select_exec(bContext *C, wmOperator *op) BLI_assert((type != SIMFACE_FREESTYLE) || (face_data_value != SIMFACE_DATA_NONE)); if (tree != NULL) { - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); } if (tree_plane != NULL) { BLI_kdtree_4d_balance(tree_plane); @@ -446,8 +446,8 @@ static int similar_face_select_exec(bContext *C, wmOperator *op) /* We are treating the normals as coordinates, the "nearest" one will * also be the one closest to the angle. */ - KDTreeNearest nearest; - if (BLI_kdtree_find_nearest(tree, normal, &nearest) != -1) { + KDTreeNearest_3d nearest; + if (BLI_kdtree_3d_find_nearest(tree, normal, &nearest) != -1) { if (angle_normalized_v3v3(normal, nearest.co) <= thresh_radians) { select = true; } @@ -550,7 +550,7 @@ face_select_all: } MEM_freeN(objects); - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); BLI_kdtree_4d_free(tree_plane); if (gset != NULL) { BLI_gset_free(gset, NULL); @@ -671,7 +671,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op) return OPERATOR_CANCELLED; } - KDTree *tree = NULL; + KDTree_3d *tree = NULL; GSet *gset = NULL; int edge_data_value = SIMEDGE_DATA_NONE; @@ -681,7 +681,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op) case SIMEDGE_FACE_ANGLE: case SIMEDGE_LENGTH: case SIMEDGE_DIR: - tree = BLI_kdtree_new(tot_edges_selected_all); + tree = BLI_kdtree_3d_new(tot_edges_selected_all); break; case SIMEDGE_FACE: gset = BLI_gset_ptr_new("Select similar edge: face"); @@ -721,7 +721,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op) { if (!CustomData_has_layer(&bm->edata, custom_data_type)) { float dummy[3] = {0.0f, 0.0f, 0.0f}; - BLI_kdtree_insert(tree, tree_index++, dummy); + BLI_kdtree_3d_insert(tree, tree_index++, dummy); continue; } break; @@ -745,14 +745,14 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op) { float dir[3]; edge_pos_direction_worldspace_get(ob, edge, dir); - BLI_kdtree_insert(tree, tree_index++, dir); + BLI_kdtree_3d_insert(tree, tree_index++, dir); break; } case SIMEDGE_LENGTH: { float length = edge_length_squared_worldspace_get(ob, edge); float dummy[3] = {length, 0.0f, 0.0f}; - BLI_kdtree_insert(tree, tree_index++, dummy); + BLI_kdtree_3d_insert(tree, tree_index++, dummy); break; } case SIMEDGE_FACE_ANGLE: @@ -760,7 +760,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op) if (BM_edge_face_count_at_most(edge, 2) == 2) { float angle = BM_edge_calc_face_angle_with_imat3(edge, ob_m3_inv); float dummy[3] = {angle, 0.0f, 0.0f}; - BLI_kdtree_insert(tree, tree_index++, dummy); + BLI_kdtree_3d_insert(tree, tree_index++, dummy); } break; } @@ -794,7 +794,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op) { const float *value = CustomData_bmesh_get(&bm->edata, edge->head.data, custom_data_type); float dummy[3] = {*value, 0.0f, 0.0f}; - BLI_kdtree_insert(tree, tree_index++, dummy); + BLI_kdtree_3d_insert(tree, tree_index++, dummy); break; } } @@ -805,7 +805,7 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op) BLI_assert((type != SIMEDGE_FREESTYLE) || (edge_data_value != SIMEDGE_DATA_NONE)); if (tree != NULL) { - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); } for (uint ob_index = 0; ob_index < objects_len; ob_index++) { @@ -873,8 +873,8 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op) /* We are treating the direction as coordinates, the "nearest" one will * also be the one closest to the intended direction. */ - KDTreeNearest nearest; - if (BLI_kdtree_find_nearest(tree, dir, &nearest) != -1) { + KDTreeNearest_3d nearest; + if (BLI_kdtree_3d_find_nearest(tree, dir, &nearest) != -1) { if (angle_normalized_v3v3(dir, nearest.co) <= thresh_radians) { select = true; } @@ -987,7 +987,7 @@ edge_select_all: } MEM_freeN(objects); - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); if (gset != NULL) { BLI_gset_free(gset, NULL); } @@ -1026,12 +1026,12 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op) return OPERATOR_CANCELLED; } - KDTree *tree = NULL; + KDTree_3d *tree = NULL; GSet *gset = NULL; switch (type) { case SIMVERT_NORMAL: - tree = BLI_kdtree_new(tot_verts_selected_all); + tree = BLI_kdtree_3d_new(tot_verts_selected_all); break; case SIMVERT_EDGE: case SIMVERT_FACE: @@ -1081,7 +1081,7 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op) mul_transposed_mat3_m4_v3(ob->imat, normal); normalize_v3(normal); - BLI_kdtree_insert(tree, normal_tree_index++, normal); + BLI_kdtree_3d_insert(tree, normal_tree_index++, normal); break; } case SIMVERT_VGROUP: @@ -1123,7 +1123,7 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op) /* Remove duplicated entries. */ if (tree != NULL) { - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); } /* Run .the BM operators. */ @@ -1204,8 +1204,8 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op) /* We are treating the normals as coordinates, the "nearest" one will * also be the one closest to the angle. */ - KDTreeNearest nearest; - if (BLI_kdtree_find_nearest(tree, normal, &nearest) != -1) { + KDTreeNearest_3d nearest; + if (BLI_kdtree_3d_find_nearest(tree, normal, &nearest) != -1) { if (angle_normalized_v3v3(normal, nearest.co) <= thresh_radians) { select = true; } @@ -1243,7 +1243,7 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op) } MEM_freeN(objects); - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); if (gset != NULL) { BLI_gset_free(gset, NULL); } diff --git a/source/blender/editors/mesh/editmesh_utils.c b/source/blender/editors/mesh/editmesh_utils.c index ed6ab38e5ab..68a2f382278 100644 --- a/source/blender/editors/mesh/editmesh_utils.c +++ b/source/blender/editors/mesh/editmesh_utils.c @@ -1006,7 +1006,7 @@ void EDBM_verts_mirror_cache_begin_ex( const float maxdist_sq = SQUARE(maxdist); /* one or the other is used depending if topo is enabled */ - KDTree *tree = NULL; + KDTree_3d *tree = NULL; MirrTopoStore_t mesh_topo_store = {NULL, -1, -1, -1}; BM_mesh_elem_table_ensure(bm, BM_VERT); @@ -1032,11 +1032,11 @@ void EDBM_verts_mirror_cache_begin_ex( ED_mesh_mirrtopo_init(me, NULL, &mesh_topo_store, true); } else { - tree = BLI_kdtree_new(bm->totvert); + tree = BLI_kdtree_3d_new(bm->totvert); BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) { - BLI_kdtree_insert(tree, i, v->co); + BLI_kdtree_3d_insert(tree, i, v->co); } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); } #define VERT_INTPTR(_v, _i) r_index ? &r_index[_i] : BM_ELEM_CD_GET_VOID_P(_v, cd_vmirr_offset); @@ -1062,7 +1062,7 @@ void EDBM_verts_mirror_cache_begin_ex( co[axis] *= -1.0f; v_mirr = NULL; - i_mirr = BLI_kdtree_find_nearest(tree, co, NULL); + i_mirr = BLI_kdtree_3d_find_nearest(tree, co, NULL); if (i_mirr != -1) { BMVert *v_test = BM_vert_at_index(bm, i_mirr); if (len_squared_v3v3(co, v_test->co) < maxdist_sq) { @@ -1090,7 +1090,7 @@ void EDBM_verts_mirror_cache_begin_ex( ED_mesh_mirrtopo_free(&mesh_topo_store); } else { - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); } } diff --git a/source/blender/editors/mesh/mesh_mirror.c b/source/blender/editors/mesh/mesh_mirror.c index 3d49d874503..a1859bf70b0 100644 --- a/source/blender/editors/mesh/mesh_mirror.c +++ b/source/blender/editors/mesh/mesh_mirror.c @@ -51,8 +51,8 @@ int ED_mesh_mirror_spatial_table(Object *ob, BMEditMesh *em, Mesh *me_eval, cons ED_mesh_mirror_spatial_table(ob, em, me_eval, NULL, 's'); if (MirrKdStore.tree) { - KDTreeNearest nearest; - const int i = BLI_kdtree_find_nearest(MirrKdStore.tree, co, &nearest); + KDTreeNearest_3d nearest; + const int i = BLI_kdtree_3d_find_nearest(MirrKdStore.tree, co, &nearest); if (i != -1) { if (nearest.dist < KD_THRESH) { @@ -70,7 +70,7 @@ int ED_mesh_mirror_spatial_table(Object *ob, BMEditMesh *em, Mesh *me_eval, cons if (MirrKdStore.tree) /* happens when entering this call without ending it */ ED_mesh_mirror_spatial_table(ob, em, me_eval, co, 'e'); - MirrKdStore.tree = BLI_kdtree_new(totvert); + MirrKdStore.tree = BLI_kdtree_3d_new(totvert); if (use_em) { BMVert *eve; @@ -81,7 +81,7 @@ int ED_mesh_mirror_spatial_table(Object *ob, BMEditMesh *em, Mesh *me_eval, cons BM_mesh_elem_table_ensure(em->bm, BM_VERT); BM_ITER_MESH_INDEX (eve, &iter, em->bm, BM_VERTS_OF_MESH, i) { - BLI_kdtree_insert(MirrKdStore.tree, i, eve->co); + BLI_kdtree_3d_insert(MirrKdStore.tree, i, eve->co); } } else { @@ -89,15 +89,15 @@ int ED_mesh_mirror_spatial_table(Object *ob, BMEditMesh *em, Mesh *me_eval, cons int i; for (i = 0; i < totvert; i++, mvert++) { - BLI_kdtree_insert(MirrKdStore.tree, i, mvert->co); + BLI_kdtree_3d_insert(MirrKdStore.tree, i, mvert->co); } } - BLI_kdtree_balance(MirrKdStore.tree); + BLI_kdtree_3d_balance(MirrKdStore.tree); } else if (mode == 'e') { /* end table */ if (MirrKdStore.tree) { - BLI_kdtree_free(MirrKdStore.tree); + BLI_kdtree_3d_free(MirrKdStore.tree); MirrKdStore.tree = NULL; } } diff --git a/source/blender/editors/metaball/mball_edit.c b/source/blender/editors/metaball/mball_edit.c index 2af78261b87..d8e5b2cba89 100644 --- a/source/blender/editors/metaball/mball_edit.c +++ b/source/blender/editors/metaball/mball_edit.c @@ -194,7 +194,7 @@ static const EnumPropertyItem prop_similar_types[] = { {0, NULL, 0, NULL, NULL}, }; -static void mball_select_similar_type_get(Object *obedit, MetaBall *mb, int type, KDTree *r_tree) +static void mball_select_similar_type_get(Object *obedit, MetaBall *mb, int type, KDTree_3d *r_tree) { float tree_entry[3] = {0.0f, 0.0f, 0.0f}; MetaElem *ml; @@ -231,12 +231,12 @@ static void mball_select_similar_type_get(Object *obedit, MetaBall *mb, int typ break; } } - BLI_kdtree_insert(r_tree, tree_index++, tree_entry); + BLI_kdtree_3d_insert(r_tree, tree_index++, tree_entry); } } } -static bool mball_select_similar_type(Object *obedit, MetaBall *mb, int type, const KDTree *tree, const float thresh) +static bool mball_select_similar_type(Object *obedit, MetaBall *mb, int type, const KDTree_3d *tree, const float thresh) { MetaElem *ml; bool changed = false; @@ -277,8 +277,8 @@ static bool mball_select_similar_type(Object *obedit, MetaBall *mb, int type, co float thresh_cos = cosf(thresh * (float)M_PI_2); - KDTreeNearest nearest; - if (BLI_kdtree_find_nearest(tree, dir, &nearest) != -1) { + KDTreeNearest_3d nearest; + if (BLI_kdtree_3d_find_nearest(tree, dir, &nearest) != -1) { float orient = angle_normalized_v3v3(dir, nearest.co); /* Map to 0-1 to compare orientation. */ float delta = thresh_cos - fabsf(cosf(orient)); @@ -311,10 +311,10 @@ static int mball_select_similar_exec(bContext *C, wmOperator *op) tot_mball_selected_all = BKE_mball_select_count_multi(objects, objects_len); short type_ref = 0; - KDTree *tree = NULL; + KDTree_3d *tree = NULL; if (type != SIMMBALL_TYPE) { - tree = BLI_kdtree_new(tot_mball_selected_all); + tree = BLI_kdtree_3d_new(tot_mball_selected_all); } /* Get type of selected MetaBall */ @@ -346,7 +346,7 @@ static int mball_select_similar_exec(bContext *C, wmOperator *op) } if (tree != NULL) { - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); } /* Select MetaBalls with desired type. */ for (uint ob_index = 0; ob_index < objects_len; ob_index++) { @@ -385,7 +385,7 @@ static int mball_select_similar_exec(bContext *C, wmOperator *op) MEM_freeN(objects); if (tree != NULL) { - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); } return OPERATOR_FINISHED; } diff --git a/source/blender/editors/object/object_relations.c b/source/blender/editors/object/object_relations.c index 6495575b76a..81925f42113 100644 --- a/source/blender/editors/object/object_relations.c +++ b/source/blender/editors/object/object_relations.c @@ -837,14 +837,14 @@ bool ED_object_parent_set(ReportList *reports, const bContext *C, Scene *scene, -static void parent_set_vert_find(KDTree *tree, Object *child, int vert_par[3], bool is_tri) +static void parent_set_vert_find(KDTree_3d *tree, Object *child, int vert_par[3], bool is_tri) { const float *co_find = child->obmat[3]; if (is_tri) { - KDTreeNearest nearest[3]; + KDTreeNearest_3d nearest[3]; int tot; - tot = BLI_kdtree_find_nearest_n(tree, co_find, nearest, 3); + tot = BLI_kdtree_3d_find_nearest_n(tree, co_find, nearest, 3); BLI_assert(tot == 3); UNUSED_VARS(tot); @@ -855,7 +855,7 @@ static void parent_set_vert_find(KDTree *tree, Object *child, int vert_par[3], b BLI_assert(min_iii(UNPACK3(vert_par)) >= 0); } else { - vert_par[0] = BLI_kdtree_find_nearest(tree, co_find, NULL); + vert_par[0] = BLI_kdtree_3d_find_nearest(tree, co_find, NULL); BLI_assert(vert_par[0] >= 0); vert_par[1] = 0; vert_par[2] = 0; @@ -876,7 +876,7 @@ static int parent_set_exec(bContext *C, wmOperator *op) const bool is_vert_par = ELEM(partype, PAR_VERTEX, PAR_VERTEX_TRI); const bool is_tri = partype == PAR_VERTEX_TRI; int tree_tot; - struct KDTree *tree = NULL; + struct KDTree_3d *tree = NULL; int vert_par[3] = {0, 0, 0}; const int *vert_par_p = is_vert_par ? vert_par : NULL; @@ -908,7 +908,7 @@ static int parent_set_exec(bContext *C, wmOperator *op) } if (is_vert_par) { - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); } if (!ok) diff --git a/source/blender/editors/physics/particle_edit.c b/source/blender/editors/physics/particle_edit.c index 78b677677bc..e4f17ca68f0 100644 --- a/source/blender/editors/physics/particle_edit.c +++ b/source/blender/editors/physics/particle_edit.c @@ -150,7 +150,7 @@ void PE_free_ptcache_edit(PTCacheEdit *edit) } if (edit->emitter_field) { - BLI_kdtree_free(edit->emitter_field); + BLI_kdtree_3d_free(edit->emitter_field); edit->emitter_field = 0; } @@ -883,8 +883,8 @@ static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys) { PTCacheEdit *edit; ParticleSystemModifierData *psmd_eval; - KDTree *tree; - KDTreeNearest nearest; + KDTree_3d *tree; + KDTreeNearest_3d nearest; HairKey *key; PARTICLE_P; float mat[4][4], co[3]; @@ -897,7 +897,7 @@ static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys) if (!psmd_eval->mesh_final) return; - tree = BLI_kdtree_new(totpart); + tree = BLI_kdtree_3d_new(totpart); /* insert particles into kd tree */ LOOP_PARTICLES { @@ -905,10 +905,10 @@ static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys) psys_mat_hair_to_orco(ob, psmd_eval->mesh_final, psys->part->from, pa, mat); copy_v3_v3(co, key->co); mul_m4_v3(mat, co); - BLI_kdtree_insert(tree, p, co); + BLI_kdtree_3d_insert(tree, p, co); } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); /* lookup particles and set in mirror cache */ if (!edit->mirror_cache) @@ -921,7 +921,7 @@ static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys) mul_m4_v3(mat, co); co[0] = -co[0]; - index = BLI_kdtree_find_nearest(tree, co, &nearest); + index = BLI_kdtree_3d_find_nearest(tree, co, &nearest); /* this needs a custom threshold still, duplicated for editmode mirror */ if (index != -1 && index != p && (nearest.dist <= 0.0002f)) @@ -939,7 +939,7 @@ static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys) } } - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); } static void PE_mirror_particle(Object *ob, Mesh *mesh, ParticleSystem *psys, ParticleData *pa, ParticleData *mpa) @@ -1107,7 +1107,7 @@ static void deflect_emitter_iter( dist_1st *= dist * emitterdist; } else { - index = BLI_kdtree_find_nearest(edit->emitter_field, key->co, NULL); + index = BLI_kdtree_3d_find_nearest(edit->emitter_field, key->co, NULL); vec = edit->emitter_cosnos + index * 6; nor = vec + 3; @@ -1329,14 +1329,14 @@ void recalc_emitter_field(Depsgraph *UNUSED(depsgraph), Object *UNUSED(ob), Part if (edit->emitter_cosnos) MEM_freeN(edit->emitter_cosnos); - BLI_kdtree_free(edit->emitter_field); + BLI_kdtree_3d_free(edit->emitter_field); totface = mesh->totface; /*totvert=dm->getNumVerts(dm);*/ /*UNUSED*/ edit->emitter_cosnos = MEM_callocN(totface * 6 * sizeof(float), "emitter cosnos"); - edit->emitter_field = BLI_kdtree_new(totface); + edit->emitter_field = BLI_kdtree_3d_new(totface); vec = edit->emitter_cosnos; nor = vec + 3; @@ -1370,10 +1370,10 @@ void recalc_emitter_field(Depsgraph *UNUSED(depsgraph), Object *UNUSED(ob), Part normalize_v3(nor); - BLI_kdtree_insert(edit->emitter_field, i, vec); + BLI_kdtree_3d_insert(edit->emitter_field, i, vec); } - BLI_kdtree_balance(edit->emitter_field); + BLI_kdtree_3d_balance(edit->emitter_field); } static void PE_update_selection(Depsgraph *depsgraph, Scene *scene, Object *ob, int useflag) @@ -2803,8 +2803,8 @@ static int remove_doubles_exec(bContext *C, wmOperator *op) PTCacheEdit *edit = PE_get_current(scene, ob); ParticleSystem *psys = edit->psys; ParticleSystemModifierData *psmd_eval; - KDTree *tree; - KDTreeNearest nearest[10]; + KDTree_3d *tree; + KDTreeNearest_3d nearest[10]; POINT_P; float mat[4][4], co[3], threshold = RNA_float_get(op->ptr, "threshold"); int n, totn, removed, totremoved; @@ -2819,17 +2819,17 @@ static int remove_doubles_exec(bContext *C, wmOperator *op) do { removed = 0; - tree = BLI_kdtree_new(psys->totpart); + tree = BLI_kdtree_3d_new(psys->totpart); /* insert particles into kd tree */ LOOP_SELECTED_POINTS { psys_mat_hair_to_object(ob, psmd_eval->mesh_final, psys->part->from, psys->particles + p, mat); copy_v3_v3(co, point->keys->co); mul_m4_v3(mat, co); - BLI_kdtree_insert(tree, p, co); + BLI_kdtree_3d_insert(tree, p, co); } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); /* tag particles to be removed */ LOOP_SELECTED_POINTS { @@ -2837,7 +2837,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_nearest_n(tree, co, nearest, 10); + totn = BLI_kdtree_3d_find_nearest_n(tree, co, nearest, 10); for (n = 0; n < totn; n++) { /* this needs a custom threshold still */ @@ -2850,7 +2850,7 @@ static int remove_doubles_exec(bContext *C, wmOperator *op) } } - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); /* remove tagged particles - don't do mirror here! */ remove_tagged_particles(ob, psys, 0); @@ -3431,7 +3431,7 @@ static void brush_puff(PEData *data, int point_index, float mouse_distance) * ob->imat is set before calling */ mul_v3_m4v3(kco, data->ob->imat, co); - point_index = BLI_kdtree_find_nearest(edit->emitter_field, kco, NULL); + point_index = BLI_kdtree_3d_find_nearest(edit->emitter_field, kco, NULL); if (point_index == -1) return; copy_v3_v3(co_root, co); @@ -3518,7 +3518,7 @@ static void brush_puff(PEData *data, int point_index, float mouse_distance) * ob->imat is set before calling */ mul_v3_m4v3(kco, data->ob->imat, oco); - point_index = BLI_kdtree_find_nearest(edit->emitter_field, kco, NULL); + point_index = BLI_kdtree_3d_find_nearest(edit->emitter_field, kco, NULL); if (point_index != -1) { copy_v3_v3(onor, &edit->emitter_cosnos[point_index * 6 + 3]); mul_mat3_m4_v3(data->ob->obmat, onor); /* normal into worldspace */ @@ -3963,7 +3963,7 @@ static int brush_add(const bContext *C, PEData *data, short number) if (n) { int newtotpart = totpart + n; float hairmat[4][4], cur_co[3]; - KDTree *tree = 0; + KDTree_3d *tree = 0; ParticleData *pa, *new_pars = MEM_callocN(newtotpart * sizeof(ParticleData), "ParticleData new"); PTCacheEditPoint *point, *new_points = MEM_callocN(newtotpart * sizeof(PTCacheEditPoint), "PTCacheEditPoint array new"); PTCacheEditKey *key; @@ -3987,14 +3987,14 @@ static int brush_add(const bContext *C, PEData *data, short number) /* create tree for interpolation */ if (pset->flag & PE_INTERPOLATE_ADDED && psys->totpart) { - tree = BLI_kdtree_new(psys->totpart); + tree = BLI_kdtree_3d_new(psys->totpart); for (i = 0, pa = psys->particles; i < totpart; i++, pa++) { psys_particle_on_dm(psmd_eval->mesh_final, psys->part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, cur_co, 0, 0, 0, 0); - BLI_kdtree_insert(tree, i, cur_co); + BLI_kdtree_3d_insert(tree, i, cur_co); } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); } edit->totpoint = psys->totpart = newtotpart; @@ -4030,12 +4030,12 @@ static int brush_add(const bContext *C, PEData *data, short number) ParticleData *ppa; HairKey *thkey; ParticleKey key3[3]; - KDTreeNearest ptn[3]; + KDTreeNearest_3d ptn[3]; int w, maxw; float maxd, totw = 0.0, weight[3]; psys_particle_on_dm(psmd_eval->mesh_final, psys->part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, co1, 0, 0, 0, 0); - maxw = BLI_kdtree_find_nearest_n(tree, co1, ptn, 3); + maxw = BLI_kdtree_3d_find_nearest_n(tree, co1, ptn, 3); maxd = ptn[maxw - 1].dist; @@ -4106,7 +4106,7 @@ static int brush_add(const bContext *C, PEData *data, short number) } if (tree) - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); } MEM_freeN(add_pars); diff --git a/source/blender/editors/util/select_utils.c b/source/blender/editors/util/select_utils.c index 80b103e0c4b..b2784aca7fa 100644 --- a/source/blender/editors/util/select_utils.c +++ b/source/blender/editors/util/select_utils.c @@ -97,7 +97,7 @@ int ED_select_similar_compare_float(const float delta, const float thresh, const } } -bool ED_select_similar_compare_float_tree(const KDTree *tree, const float length, const float thresh, const int compare) +bool ED_select_similar_compare_float_tree(const KDTree_3d *tree, const float length, const float thresh, const int compare) { /* Length of the edge we want to compare against. */ float nearest_edge_length; @@ -123,9 +123,9 @@ bool ED_select_similar_compare_float_tree(const KDTree *tree, const float length return false; } - KDTreeNearest nearest; + KDTreeNearest_3d nearest; float dummy[3] = {nearest_edge_length, 0.0f, 0.0f}; - if (BLI_kdtree_find_nearest(tree, dummy, &nearest) != -1) { + if (BLI_kdtree_3d_find_nearest(tree, dummy, &nearest) != -1) { float delta = length - nearest.co[0]; return ED_select_similar_compare_float(delta, thresh, compare); } diff --git a/source/blender/editors/uvedit/uvedit_ops.c b/source/blender/editors/uvedit/uvedit_ops.c index f771feeff2c..108481b9dae 100644 --- a/source/blender/editors/uvedit/uvedit_ops.c +++ b/source/blender/editors/uvedit/uvedit_ops.c @@ -1853,7 +1853,7 @@ static int uv_remove_doubles_to_selected(bContext *C, wmOperator *op) uv_maxlen += em->bm->totloop; } - KDTree *tree = BLI_kdtree_new(uv_maxlen); + KDTree_3d *tree = BLI_kdtree_3d_new(uv_maxlen); int *duplicates = NULL; BLI_array_declare(duplicates); @@ -1886,7 +1886,7 @@ static int uv_remove_doubles_to_selected(bContext *C, wmOperator *op) if (uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) { MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset); copy_v3_fl3(uvw, luv->uv[0], luv->uv[1], 0.0f); - BLI_kdtree_insert(tree, mloopuv_count, uvw); + BLI_kdtree_3d_insert(tree, mloopuv_count, uvw); BLI_array_append(duplicates, -1); BLI_array_append(mloopuv_arr, luv); mloopuv_count++; @@ -1897,8 +1897,8 @@ static int uv_remove_doubles_to_selected(bContext *C, wmOperator *op) ob_mloopuv_max_idx[ob_index] = mloopuv_count - 1; } - BLI_kdtree_balance(tree); - int found_duplicates = BLI_kdtree_calc_duplicates_fast(tree, threshold, false, duplicates); + BLI_kdtree_3d_balance(tree); + int found_duplicates = BLI_kdtree_3d_calc_duplicates_fast(tree, threshold, false, duplicates); if (found_duplicates > 0) { /* Calculate average uv for duplicates. */ @@ -1955,7 +1955,7 @@ static int uv_remove_doubles_to_selected(bContext *C, wmOperator *op) } } - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); BLI_array_free(mloopuv_arr); BLI_array_free(duplicates); MEM_freeN(changed); @@ -1987,7 +1987,7 @@ static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op) uv_maxlen += em->bm->totloop; } - KDTree *tree = BLI_kdtree_new(uv_maxlen); + KDTree_3d *tree = BLI_kdtree_3d_new(uv_maxlen); MLoopUV **mloopuv_arr = NULL; BLI_array_declare(mloopuv_arr); @@ -2018,7 +2018,7 @@ static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op) if (!uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) { MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset); copy_v3_fl3(uvw, luv->uv[0], luv->uv[1], 0.0f); - BLI_kdtree_insert(tree, mloopuv_count, uvw); + BLI_kdtree_3d_insert(tree, mloopuv_count, uvw); BLI_array_append(mloopuv_arr, luv); mloopuv_count++; } @@ -2026,7 +2026,7 @@ static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op) } } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); /* For each selected uv, find duplicate non selected uv. */ for (uint ob_index = 0; ob_index < objects_len; ob_index++) { @@ -2053,8 +2053,8 @@ static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op) MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset); copy_v3_fl3(uvw, luv->uv[0], luv->uv[1], 0.0f); - KDTreeNearest nearest; - const int i = BLI_kdtree_find_nearest(tree, uvw, &nearest); + KDTreeNearest_3d nearest; + const int i = BLI_kdtree_3d_find_nearest(tree, uvw, &nearest); if (i != -1 && nearest.dist < threshold) { copy_v2_v2(luv->uv, mloopuv_arr[i]->uv); @@ -2071,7 +2071,7 @@ static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op) } } - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); BLI_array_free(mloopuv_arr); MEM_freeN(objects); diff --git a/source/blender/makesdna/DNA_boid_types.h b/source/blender/makesdna/DNA_boid_types.h index 6a0a19fa44c..6c68ca69363 100644 --- a/source/blender/makesdna/DNA_boid_types.h +++ b/source/blender/makesdna/DNA_boid_types.h @@ -186,7 +186,7 @@ typedef struct BoidState { //typedef struct BoidSimulationData { // ListBase signal_defines;/* list of defined signals */ // ListBase signals[20]; /* gathers signals from all channels */ -// struct KDTree *signaltrees[20]; +// struct KDTree_3d *signaltrees[20]; // char channel_names[20][32]; // int last_signal_id; /* used for incrementing signal ids */ // int flag; /* switches for drawing stuff */ diff --git a/source/blender/makesdna/DNA_particle_types.h b/source/blender/makesdna/DNA_particle_types.h index 7a7c30950cc..ae677a93c43 100644 --- a/source/blender/makesdna/DNA_particle_types.h +++ b/source/blender/makesdna/DNA_particle_types.h @@ -379,7 +379,7 @@ typedef struct ParticleSystem { int tot_fluidsprings, alloc_fluidsprings; /** Used for interactions with self and other systems. */ - struct KDTree *tree; + struct KDTree_3d *tree; /** Used for interactions with self and other systems. */ struct BVHTree *bvhtree; diff --git a/source/blender/modifiers/intern/MOD_explode.c b/source/blender/modifiers/intern/MOD_explode.c index e7e76f58c93..9c13f05daa1 100644 --- a/source/blender/modifiers/intern/MOD_explode.c +++ b/source/blender/modifiers/intern/MOD_explode.c @@ -94,7 +94,7 @@ static void createFacepa( MFace *fa = NULL, *mface = NULL; MVert *mvert = NULL; ParticleData *pa; - KDTree *tree; + KDTree_3d *tree; RNG *rng; float center[3], co[3]; int *facepa = NULL, *vertpa = NULL, totvert = 0, totface = 0, totpart = 0; @@ -138,12 +138,12 @@ static void createFacepa( } /* make tree of emitter locations */ - tree = BLI_kdtree_new(totpart); + tree = BLI_kdtree_3d_new(totpart); for (p = 0, pa = psys->particles; p < totpart; p++, pa++) { psys_particle_on_emitter(psmd, psys->part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, co, NULL, NULL, NULL, NULL); - BLI_kdtree_insert(tree, p, co); + BLI_kdtree_3d_insert(tree, p, co); } - BLI_kdtree_balance(tree); + BLI_kdtree_3d_balance(tree); /* set face-particle-indexes to nearest particle to face center */ for (i = 0, fa = mface; i < totface; i++, fa++) { @@ -157,7 +157,7 @@ static void createFacepa( mul_v3_fl(center, 1.0f / 3.0f); } - p = BLI_kdtree_find_nearest(tree, center, NULL); + p = BLI_kdtree_3d_find_nearest(tree, center, NULL); v1 = vertpa[fa->v1]; v2 = vertpa[fa->v2]; @@ -187,7 +187,7 @@ static void createFacepa( if (vertpa) { MEM_freeN(vertpa); } - BLI_kdtree_free(tree); + BLI_kdtree_3d_free(tree); BLI_rng_free(rng); } diff --git a/source/blender/python/mathutils/mathutils.c b/source/blender/python/mathutils/mathutils.c index 60224d093a1..f577ef3b441 100644 --- a/source/blender/python/mathutils/mathutils.c +++ b/source/blender/python/mathutils/mathutils.c @@ -655,7 +655,7 @@ PyMODINIT_FUNC PyInit_mathutils(void) PyModule_AddObject(mod, "bvhtree", (submodule = PyInit_mathutils_bvhtree())); PyDict_SetItem(sys_modules, PyModule_GetNameObject(submodule), submodule); - /* KDTree submodule */ + /* KDTree_3d submodule */ PyModule_AddObject(mod, "kdtree", (submodule = PyInit_mathutils_kdtree())); PyDict_SetItem(sys_modules, PyModule_GetNameObject(submodule), submodule); #endif diff --git a/source/blender/python/mathutils/mathutils_kdtree.c b/source/blender/python/mathutils/mathutils_kdtree.c index 43aaae6ad99..f9cc99551bb 100644 --- a/source/blender/python/mathutils/mathutils_kdtree.c +++ b/source/blender/python/mathutils/mathutils_kdtree.c @@ -38,7 +38,7 @@ typedef struct { PyObject_HEAD - KDTree *obj; + KDTree_3d *obj; unsigned int maxsize; unsigned int count; unsigned int count_balance; /* size when we last balanced */ @@ -48,7 +48,7 @@ typedef struct { /* -------------------------------------------------------------------- */ /* Utility helper functions */ -static void kdtree_nearest_to_py_tuple(const KDTreeNearest *nearest, PyObject *py_retval) +static void kdtree_nearest_to_py_tuple(const KDTreeNearest_3d *nearest, PyObject *py_retval) { BLI_assert(nearest->index >= 0); BLI_assert(PyTuple_GET_SIZE(py_retval) == 3); @@ -59,7 +59,7 @@ static void kdtree_nearest_to_py_tuple(const KDTreeNearest *nearest, PyObject *p PyFloat_FromDouble(nearest->dist)); } -static PyObject *kdtree_nearest_to_py(const KDTreeNearest *nearest) +static PyObject *kdtree_nearest_to_py(const KDTreeNearest_3d *nearest) { PyObject *py_retval; @@ -70,7 +70,7 @@ static PyObject *kdtree_nearest_to_py(const KDTreeNearest *nearest) return py_retval; } -static PyObject *kdtree_nearest_to_py_and_check(const KDTreeNearest *nearest) +static PyObject *kdtree_nearest_to_py_and_check(const KDTreeNearest_3d *nearest) { PyObject *py_retval; @@ -110,7 +110,7 @@ static int PyKDTree__tp_init(PyKDTree *self, PyObject *args, PyObject *kwargs) return -1; } - self->obj = BLI_kdtree_new(maxsize); + self->obj = BLI_kdtree_3d_new(maxsize); self->maxsize = maxsize; self->count = 0; self->count_balance = 0; @@ -120,7 +120,7 @@ static int PyKDTree__tp_init(PyKDTree *self, PyObject *args, PyObject *kwargs) static void PyKDTree__tp_dealloc(PyKDTree *self) { - BLI_kdtree_free(self->obj); + BLI_kdtree_3d_free(self->obj); Py_TYPE(self)->tp_free((PyObject *)self); } @@ -161,7 +161,7 @@ static PyObject *py_kdtree_insert(PyKDTree *self, PyObject *args, PyObject *kwar return NULL; } - BLI_kdtree_insert(self->obj, index, co); + BLI_kdtree_3d_insert(self->obj, index, co); self->count++; Py_RETURN_NONE; @@ -178,7 +178,7 @@ PyDoc_STRVAR(py_kdtree_balance_doc, ); static PyObject *py_kdtree_balance(PyKDTree *self) { - BLI_kdtree_balance(self->obj); + BLI_kdtree_3d_balance(self->obj); self->count_balance = self->count; Py_RETURN_NONE; } @@ -228,7 +228,7 @@ static PyObject *py_kdtree_find(PyKDTree *self, PyObject *args, PyObject *kwargs { PyObject *py_co, *py_filter = NULL; float co[3]; - KDTreeNearest nearest; + KDTreeNearest_3d nearest; const char *keywords[] = {"co", "filter", NULL}; if (!PyArg_ParseTupleAndKeywords( @@ -249,7 +249,7 @@ static PyObject *py_kdtree_find(PyKDTree *self, PyObject *args, PyObject *kwargs nearest.index = -1; if (py_filter == NULL) { - BLI_kdtree_find_nearest(self->obj, co, &nearest); + BLI_kdtree_3d_find_nearest(self->obj, co, &nearest); } else { struct PyKDTree_NearestData data = {0}; @@ -257,7 +257,7 @@ static PyObject *py_kdtree_find(PyKDTree *self, PyObject *args, PyObject *kwargs data.py_filter = py_filter; data.is_error = false; - BLI_kdtree_find_nearest_cb( + BLI_kdtree_3d_find_nearest_cb( self->obj, co, py_find_nearest_cb, &data, &nearest); @@ -287,7 +287,7 @@ static PyObject *py_kdtree_find_n(PyKDTree *self, PyObject *args, PyObject *kwar PyObject *py_list; PyObject *py_co; float co[3]; - KDTreeNearest *nearest; + KDTreeNearest_3d *nearest; unsigned int n; int i, found; const char *keywords[] = {"co", "n", NULL}; @@ -312,9 +312,9 @@ static PyObject *py_kdtree_find_n(PyKDTree *self, PyObject *args, PyObject *kwar return NULL; } - nearest = MEM_mallocN(sizeof(KDTreeNearest) * n, __func__); + nearest = MEM_mallocN(sizeof(KDTreeNearest_3d) * n, __func__); - found = BLI_kdtree_find_nearest_n(self->obj, co, nearest, n); + found = BLI_kdtree_3d_find_nearest_n(self->obj, co, nearest, n); py_list = PyList_New(found); @@ -344,7 +344,7 @@ static PyObject *py_kdtree_find_range(PyKDTree *self, PyObject *args, PyObject * PyObject *py_list; PyObject *py_co; float co[3]; - KDTreeNearest *nearest = NULL; + KDTreeNearest_3d *nearest = NULL; float radius; int i, found; @@ -370,7 +370,7 @@ static PyObject *py_kdtree_find_range(PyKDTree *self, PyObject *args, PyObject * return NULL; } - found = BLI_kdtree_range_search(self->obj, co, &nearest, radius); + found = BLI_kdtree_3d_range_search(self->obj, co, &nearest, radius); py_list = PyList_New(found); |