[Bf-blender-cvs] [899fc0331c4] master: BLI_kdtree: use 1d tree for select similar
Campbell Barton
noreply at git.blender.org
Tue Mar 19 16:13:31 CET 2019
Commit: 899fc0331c40bb8ca6d3673a418fe7ee90c3613a
Author: Campbell Barton
Date: Wed Mar 20 01:56:53 2019 +1100
Branches: master
https://developer.blender.org/rB899fc0331c40bb8ca6d3673a418fe7ee90c3613a
BLI_kdtree: use 1d tree for select similar
===================================================================
M source/blender/editors/curve/editcurve_select.c
M source/blender/editors/include/ED_select_utils.h
M source/blender/editors/mesh/editmesh_select_similar.c
M source/blender/editors/metaball/mball_edit.c
M source/blender/editors/util/select_utils.c
===================================================================
diff --git a/source/blender/editors/curve/editcurve_select.c b/source/blender/editors/curve/editcurve_select.c
index ba9a42a6c2b..23d55ed8eca 100644
--- a/source/blender/editors/curve/editcurve_select.c
+++ b/source/blender/editors/curve/editcurve_select.c
@@ -1362,7 +1362,8 @@ 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_3d *r_tree)
+static void curve_nurb_selected_type_get(
+ Object *ob, Nurb *nu, const int type, KDTree_1d *tree_1d, KDTree_3d *tree_3d)
{
float tree_entry[3] = {0.0f, 0.0f, 0.0f};
@@ -1393,7 +1394,12 @@ static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, K
break;
}
}
- BLI_kdtree_3d_insert(r_tree, tree_index++, tree_entry);
+ if (tree_1d) {
+ BLI_kdtree_1d_insert(tree_1d, tree_index++, tree_entry);
+ }
+ else {
+ BLI_kdtree_3d_insert(tree_3d, tree_index++, tree_entry);
+ }
}
}
}
@@ -1423,7 +1429,12 @@ static void curve_nurb_selected_type_get(Object *ob, Nurb *nu, const int type, K
break;
}
}
- BLI_kdtree_3d_insert(r_tree, tree_index++, tree_entry);
+ if (tree_1d) {
+ BLI_kdtree_1d_insert(tree_1d, tree_index++, tree_entry);
+ }
+ else {
+ BLI_kdtree_3d_insert(tree_3d, tree_index++, tree_entry);
+ }
}
}
}
@@ -1431,7 +1442,8 @@ 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_3d *tree, const float thresh, const int compare)
+ const KDTree_1d *tree_1d, const KDTree_3d *tree_3d,
+ const float thresh, const int compare)
{
const float thresh_cos = cosf(thresh * (float)M_PI_2);
bool changed = false;
@@ -1448,7 +1460,7 @@ static bool curve_nurb_select_similar_type(
case SIMCURHAND_RADIUS:
{
float radius_ref = bezt->radius;
- if (ED_select_similar_compare_float_tree(tree, radius_ref, thresh, compare)) {
+ if (ED_select_similar_compare_float_tree(tree_1d, radius_ref, thresh, compare)) {
select = true;
}
break;
@@ -1456,7 +1468,7 @@ static bool curve_nurb_select_similar_type(
case SIMCURHAND_WEIGHT:
{
float weight_ref = bezt->weight;
- if (ED_select_similar_compare_float_tree(tree, weight_ref, thresh, compare)) {
+ if (ED_select_similar_compare_float_tree(tree_1d, weight_ref, thresh, compare)) {
select = true;
}
break;
@@ -1466,7 +1478,7 @@ static bool curve_nurb_select_similar_type(
float dir[3];
nurb_bezt_direction_worldspace_get(ob, nu, bezt, dir);
KDTreeNearest_3d nearest;
- if (BLI_kdtree_3d_find_nearest(tree, dir, &nearest) != -1) {
+ if (BLI_kdtree_3d_find_nearest(tree_3d, 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)) {
@@ -1496,7 +1508,7 @@ static bool curve_nurb_select_similar_type(
case SIMCURHAND_RADIUS:
{
float radius_ref = bp->radius;
- if (ED_select_similar_compare_float_tree(tree, radius_ref, thresh, compare)) {
+ if (ED_select_similar_compare_float_tree(tree_1d, radius_ref, thresh, compare)) {
select = true;
}
break;
@@ -1504,7 +1516,7 @@ static bool curve_nurb_select_similar_type(
case SIMCURHAND_WEIGHT:
{
float weight_ref = bp->weight;
- if (ED_select_similar_compare_float_tree(tree, weight_ref, thresh, compare)) {
+ if (ED_select_similar_compare_float_tree(tree_1d, weight_ref, thresh, compare)) {
select = true;
}
break;
@@ -1514,7 +1526,7 @@ static bool curve_nurb_select_similar_type(
float dir[3];
nurb_bpoint_direction_worldspace_get(ob, nu, bp, dir);
KDTreeNearest_3d nearest;
- if (BLI_kdtree_3d_find_nearest(tree, dir, &nearest) != -1) {
+ if (BLI_kdtree_3d_find_nearest(tree_3d, 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 +1572,17 @@ static int curve_select_similar_exec(bContext *C, wmOperator *op)
return OPERATOR_CANCELLED;
}
- KDTree_3d *tree = NULL;
+ KDTree_1d *tree_1d = NULL;
+ KDTree_3d *tree_3d = NULL;
short type_ref = 0;
switch (optype) {
case SIMCURHAND_RADIUS:
case SIMCURHAND_WEIGHT:
+ tree_1d = BLI_kdtree_1d_new(tot_nurbs_selected_all);
+ break;
case SIMCURHAND_DIRECTION:
- tree = BLI_kdtree_3d_new(tot_nurbs_selected_all);
+ tree_3d = BLI_kdtree_3d_new(tot_nurbs_selected_all);
break;
}
@@ -1591,14 +1606,17 @@ static int curve_select_similar_exec(bContext *C, wmOperator *op)
case SIMCURHAND_RADIUS:
case SIMCURHAND_WEIGHT:
case SIMCURHAND_DIRECTION:
- curve_nurb_selected_type_get(obedit, nu, optype, tree);
+ curve_nurb_selected_type_get(obedit, nu, optype, tree_1d, tree_3d);
break;
}
}
}
- if (tree != NULL) {
- BLI_kdtree_3d_balance(tree);
+ if (tree_1d != NULL) {
+ BLI_kdtree_1d_balance(tree_1d);
+ }
+ if (tree_3d != NULL) {
+ BLI_kdtree_3d_balance(tree_3d);
}
/* Select control points with desired type. */
@@ -1622,7 +1640,8 @@ static int curve_select_similar_exec(bContext *C, wmOperator *op)
case SIMCURHAND_RADIUS:
case SIMCURHAND_WEIGHT:
case SIMCURHAND_DIRECTION:
- changed = curve_nurb_select_similar_type(obedit, nu, optype, tree, thresh, compare);
+ changed = curve_nurb_select_similar_type(
+ obedit, nu, optype, tree_1d, tree_3d, thresh, compare);
break;
}
}
@@ -1634,8 +1653,12 @@ static int curve_select_similar_exec(bContext *C, wmOperator *op)
}
MEM_freeN(objects);
- if (tree != NULL) {
- BLI_kdtree_3d_free(tree);
+
+ if (tree_1d != NULL) {
+ BLI_kdtree_1d_free(tree_1d);
+ }
+ if (tree_3d != NULL) {
+ BLI_kdtree_3d_free(tree_3d);
}
return OPERATOR_FINISHED;
diff --git a/source/blender/editors/include/ED_select_utils.h b/source/blender/editors/include/ED_select_utils.h
index 87045be9932..04ea1769c09 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_3d;
+struct KDTree_1d;
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_3d *tree, const float length, const float thresh, const int compare);
+bool ED_select_similar_compare_float_tree(const struct KDTree_1d *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 59610a10d96..98808fc6df3 100644
--- a/source/blender/editors/mesh/editmesh_select_similar.c
+++ b/source/blender/editors/mesh/editmesh_select_similar.c
@@ -183,8 +183,9 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
return OPERATOR_CANCELLED;
}
+ KDTree_1d *tree_1d = NULL;
KDTree_3d *tree_3d = NULL;
- KDTree_4d *tree_plane = NULL;
+ KDTree_4d *tree_4d = NULL;
GSet *gset = NULL;
GSet **gset_array = NULL;
int face_data_value = SIMFACE_DATA_NONE;
@@ -192,11 +193,13 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
switch (type) {
case SIMFACE_AREA:
case SIMFACE_PERIMETER:
+ tree_1d = BLI_kdtree_1d_new(tot_faces_selected_all);
+ break;
case SIMFACE_NORMAL:
tree_3d = BLI_kdtree_3d_new(tot_faces_selected_all);
break;
case SIMFACE_COPLANAR:
- tree_plane = BLI_kdtree_4d_new(tot_faces_selected_all);
+ tree_4d = BLI_kdtree_4d_new(tot_faces_selected_all);
break;
case SIMFACE_SIDES:
case SIMFACE_MATERIAL:
@@ -272,15 +275,13 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
case SIMFACE_AREA:
{
float area = BM_face_calc_area_with_mat3(face, ob_m3);
- float dummy[3] = {area, 0.0f, 0.0f};
- BLI_kdtree_3d_insert(tree_3d, tree_index++, dummy);
+ BLI_kdtree_1d_insert(tree_1d, tree_index++, &area);
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_3d_insert(tree_3d, tree_index++, dummy);
+ BLI_kdtree_1d_insert(tree_1d, tree_index++, &perimeter);
break;
}
case SIMFACE_NORMAL:
@@ -289,7 +290,6 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
copy_v3_v3(normal, face->no);
mul_transposed_mat3_m4_v3(ob->imat, normal);
normalize_v3(normal);
-
BLI_kdtree_3d_insert(tree_3d, tree_index++, normal);
break;
}
@@ -297,7 +297,7 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
{
float plane[4];
face_to_plane(ob, face, plane);
- BLI_kdtree_4d_insert(tree_plane, tree_index++, plane);
+ BLI_kdtree_4d_insert(tree_4d, tree_index++, plane);
break;
}
case SIMFACE_SMOOTH:
@@ -336,11 +336,14 @@ static int similar_face_select_exec(bContext *C, wmOperator *op)
BLI_assert((type != SIMFACE_FREESTYLE) || (face_data_value != SIMFACE_DATA_NONE));
+ if (tree_1d != NULL) {
+ BLI_kdtree_1d_balance(tree_1d);
+ }
if (tree_3d != NULL) {
BLI_kdtree_3d_balance(tree_3d);
}
- if (tree_plane != NULL) {
- BLI_kdtree_4d_balance(tree_plane);
+ if (tree_4d != NULL) {
+ BLI_kdtree_4d_balance(tree_4d);
}
for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
@@ -424,7 +427,7 @@ static in
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list