Cleanup: use BLI_kdtree_3d prefix
authorCampbell Barton <ideasman42@gmail.com>
Tue, 19 Mar 2019 13:46:33 +0000 (00:46 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Tue, 19 Mar 2019 13:48:51 +0000 (00:48 +1100)
Use prefix now there isn't only the 3d version.

30 files changed:
source/blender/blenkernel/BKE_object.h
source/blender/blenkernel/BKE_particle.h
source/blender/blenkernel/BKE_pointcache.h
source/blender/blenkernel/intern/boids.c
source/blender/blenkernel/intern/dynamicpaint.c
source/blender/blenkernel/intern/object.c
source/blender/blenkernel/intern/particle.c
source/blender/blenkernel/intern/particle_distribute.c
source/blender/blenkernel/intern/particle_system.c
source/blender/blenkernel/intern/smoke.c
source/blender/blenlib/BLI_kdtree.h
source/blender/blenlib/intern/kdtree_3d.c
source/blender/blenlib/intern/kdtree_impl.h
source/blender/bmesh/operators/bmo_removedoubles.c
source/blender/bmesh/tools/bmesh_decimate_collapse.c
source/blender/editors/curve/editcurve_select.c
source/blender/editors/include/ED_select_utils.h
source/blender/editors/mesh/editmesh_select_similar.c
source/blender/editors/mesh/editmesh_utils.c
source/blender/editors/mesh/mesh_mirror.c
source/blender/editors/metaball/mball_edit.c
source/blender/editors/object/object_relations.c
source/blender/editors/physics/particle_edit.c
source/blender/editors/util/select_utils.c
source/blender/editors/uvedit/uvedit_ops.c
source/blender/makesdna/DNA_boid_types.h
source/blender/makesdna/DNA_particle_types.h
source/blender/modifiers/intern/MOD_explode.c
source/blender/python/mathutils/mathutils.c
source/blender/python/mathutils/mathutils_kdtree.c

index 9e6366f..4a14707 100644 (file)
@@ -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);
 
index 56f6482..b2b7f9f 100644 (file)
@@ -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;
index 6f0145a..9cfc43b 100644 (file)
@@ -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;
 
index 8b71aa0..c092b2c 100644 (file)
@@ -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);
 
index eeaf071..0419a5a 100644 (file)
@@ -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;
 }
index 66b888c..4f8be84 100644 (file)
@@ -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;
                }
        }
index bdf0b23..4abc57c 100644 (file)
@@ -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(
index 4485afb..bbf8fec 100644 (file)
@@ -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;
index 2975eaa..28a2e6e 100644 (file)
@@ -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;
                }
index 4b9dd9a..82acc27 100644 (file)
@@ -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 */
index eb0421e..af10a44 100644 (file)
 
 /* 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 */
index 1da9377..2f85755 100644 (file)
@@ -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
index 2d4a657..62bd51e 100644 (file)
@@ -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 {
index 1432e15..eba8c37 100644 (file)
@@ -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) {
index 7f6bcf1..e5dd649 100644 (file)
@@ -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;
 }
index 25470f7..ba9a42a 100644 (file)
@@ -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;
 
index a7b9ac7..87045be 100644 (file)
@@ -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);
 
index 299db63..59c3457 100644 (file)
@@ -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);
        }
index ed6ab38..68a2f38 100644 (file)
@@ -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);
        }
 }
 
index 3d49d87..a1859bf 100644 (file)
@@ -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;
                }
        }
index 2af7826..d8e5b2c 100644 (file)
@@ -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;
 }
index 6495575..81925f4 100644 (file)
@@ -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)
index 78b6776..e4f17ca 100644 (file)
@@ -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);
index 80b103e..b2784ac 100644 (file)
@@ -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);
        }
index f771fee..108481b 100644 (file)
@@ -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);
 
index 6a0a19f..6c68ca6 100644 (file)
@@ -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 */
index 7a7c309..ae677a9 100644 (file)
@@ -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;
 
index e7e76f5..9c13f05 100644 (file)
@@ -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);
 }
index 60224d0..f577ef3 100644 (file)
@@ -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
index 43aaae6..f9cc995 100644 (file)
@@ -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);