diff options
Diffstat (limited to 'source/blender/editors/mesh/editmesh_select.c')
| -rw-r--r-- | source/blender/editors/mesh/editmesh_select.c | 664 |
1 files changed, 427 insertions, 237 deletions
diff --git a/source/blender/editors/mesh/editmesh_select.c b/source/blender/editors/mesh/editmesh_select.c index 71f1b200dda..0bdb5032a30 100644 --- a/source/blender/editors/mesh/editmesh_select.c +++ b/source/blender/editors/mesh/editmesh_select.c @@ -57,6 +57,7 @@ #include "ED_mesh.h" #include "ED_screen.h" #include "ED_uvedit.h" +#include "ED_object.h" #include "ED_view3d.h" #include "GPU_colors.h" @@ -331,9 +332,9 @@ int EDBM_backbuf_circle_init(ViewContext *vc, short xs, short ys, short rads) } -static void findnearestvert__doClosest(void *userData, BMVert *eve, int x, int y, int index) +static void findnearestvert__doClosest(void *userData, BMVert *eve, const float screen_co[2], int index) { - struct { short mval[2], pass, select, strict; int dist, lastIndex, closestIndex; BMVert *closest; } *data = userData; + struct { float mval_fl[2], pass, select, strict; float dist, lastIndex, closestIndex; BMVert *closest; } *data = userData; if (data->pass == 0) { if (index <= data->lastIndex) @@ -345,18 +346,18 @@ static void findnearestvert__doClosest(void *userData, BMVert *eve, int x, int y } if (data->dist > 3) { - int temp = abs(data->mval[0] - x) + abs(data->mval[1] - y); + float dist_test = len_manhattan_v2v2(data->mval_fl, screen_co); if (BM_elem_flag_test(eve, BM_ELEM_SELECT) == data->select) { if (data->strict == 1) { return; } else { - temp += 5; + dist_test += 5; } } - if (temp < data->dist) { - data->dist = temp; + if (dist_test < data->dist) { + data->dist = dist_test; data->closest = eve; data->closestIndex = index; } @@ -383,10 +384,10 @@ static unsigned int findnearestvert__backbufIndextest(void *handle, unsigned int * if 0, unselected vertice are given the bias * strict: if 1, the vertice corresponding to the sel parameter are ignored and not just biased */ -BMVert *EDBM_vert_find_nearest(ViewContext *vc, int *dist, short sel, short strict) +BMVert *EDBM_vert_find_nearest(ViewContext *vc, float *r_dist, const short sel, const short strict) { if (vc->v3d->drawtype > OB_WIRE && (vc->v3d->flag & V3D_ZBUF_SELECT)) { - int distance; + float distance; unsigned int index; BMVert *eve; @@ -401,8 +402,8 @@ BMVert *EDBM_vert_find_nearest(ViewContext *vc, int *dist, short sel, short stri eve = BM_vert_at_index(vc->em->bm, index - 1); - if (eve && distance < *dist) { - *dist = distance; + if (eve && distance < *r_dist) { + *r_dist = distance; return eve; } else { @@ -411,7 +412,7 @@ BMVert *EDBM_vert_find_nearest(ViewContext *vc, int *dist, short sel, short stri } else { - struct { short mval[2], pass, select, strict; int dist, lastIndex, closestIndex; BMVert *closest; } data; + struct { float mval_fl[2], pass, select, strict; float dist, lastIndex, closestIndex; BMVert *closest; } data; static int lastSelectedIndex = 0; static BMVert *lastSelected = NULL; @@ -421,10 +422,10 @@ BMVert *EDBM_vert_find_nearest(ViewContext *vc, int *dist, short sel, short stri } data.lastIndex = lastSelectedIndex; - data.mval[0] = vc->mval[0]; - data.mval[1] = vc->mval[1]; + data.mval_fl[0] = vc->mval[0]; + data.mval_fl[1] = vc->mval[1]; data.select = sel; - data.dist = *dist; + data.dist = *r_dist; data.strict = strict; data.closest = NULL; data.closestIndex = 0; @@ -433,14 +434,14 @@ BMVert *EDBM_vert_find_nearest(ViewContext *vc, int *dist, short sel, short stri ED_view3d_init_mats_rv3d(vc->obedit, vc->rv3d); - mesh_foreachScreenVert(vc, findnearestvert__doClosest, &data, V3D_CLIP_TEST_RV3D_CLIPPING); + mesh_foreachScreenVert(vc, findnearestvert__doClosest, &data, V3D_PROJ_TEST_CLIP_DEFAULT); if (data.dist > 3) { data.pass = 1; - mesh_foreachScreenVert(vc, findnearestvert__doClosest, &data, V3D_CLIP_TEST_RV3D_CLIPPING); + mesh_foreachScreenVert(vc, findnearestvert__doClosest, &data, V3D_PROJ_TEST_CLIP_DEFAULT); } - *dist = data.dist; + *r_dist = data.dist; lastSelected = data.closest; lastSelectedIndex = data.closestIndex; @@ -463,18 +464,12 @@ float labda_PdistVL2Dfl(const float v1[2], const float v2[2], const float v3[2]) } /* note; uses v3d, so needs active 3d window */ -static void findnearestedge__doClosest(void *userData, BMEdge *eed, int x0, int y0, int x1, int y1, int UNUSED(index)) +static void findnearestedge__doClosest(void *userData, BMEdge *eed, const float screen_co_a[2], const float screen_co_b[2], int UNUSED(index)) { - struct { ViewContext vc; float mval[2]; int dist; BMEdge *closest; } *data = userData; - float v1[2], v2[2]; + struct { ViewContext vc; float mval_fl[2]; float dist; BMEdge *closest; } *data = userData; int distance; - - v1[0] = x0; - v1[1] = y0; - v2[0] = x1; - v2[1] = y1; - - distance = dist_to_line_segment_v2(data->mval, v1, v2); + + distance = dist_to_line_segment_v2(data->mval_fl, screen_co_a, screen_co_b); if (BM_elem_flag_test(eed, BM_ELEM_SELECT)) { distance += 5; @@ -482,7 +477,7 @@ static void findnearestedge__doClosest(void *userData, BMEdge *eed, int x0, int if (distance < data->dist) { if (data->vc.rv3d->rflag & RV3D_CLIPPING) { - float labda = labda_PdistVL2Dfl(data->mval, v1, v2); + float labda = labda_PdistVL2Dfl(data->mval_fl, screen_co_a, screen_co_b); float vec[3]; vec[0] = eed->v1->co[0] + labda * (eed->v2->co[0] - eed->v1->co[0]); @@ -500,11 +495,11 @@ static void findnearestedge__doClosest(void *userData, BMEdge *eed, int x0, int } } } -BMEdge *EDBM_edge_find_nearest(ViewContext *vc, int *dist) +BMEdge *EDBM_edge_find_nearest(ViewContext *vc, float *r_dist) { if (vc->v3d->drawtype > OB_WIRE && (vc->v3d->flag & V3D_ZBUF_SELECT)) { - int distance; + float distance; unsigned int index; BMEdge *eed; @@ -513,8 +508,8 @@ BMEdge *EDBM_edge_find_nearest(ViewContext *vc, int *dist) index = view3d_sample_backbuf_rect(vc, vc->mval, 50, bm_solidoffs, bm_wireoffs, &distance, 0, NULL, NULL); eed = BM_edge_at_index(vc->em->bm, index - 1); - if (eed && distance < *dist) { - *dist = distance; + if (eed && distance < *r_dist) { + *r_dist = distance; return eed; } else { @@ -522,36 +517,37 @@ BMEdge *EDBM_edge_find_nearest(ViewContext *vc, int *dist) } } else { - struct { ViewContext vc; float mval[2]; int dist; BMEdge *closest; } data; + struct { ViewContext vc; float mval_fl[2]; float dist; BMEdge *closest; } data; data.vc = *vc; - data.mval[0] = vc->mval[0]; - data.mval[1] = vc->mval[1]; - data.dist = *dist; + data.mval_fl[0] = vc->mval[0]; + data.mval_fl[1] = vc->mval[1]; + data.dist = *r_dist; data.closest = NULL; ED_view3d_init_mats_rv3d(vc->obedit, vc->rv3d); - mesh_foreachScreenEdge(vc, findnearestedge__doClosest, &data, V3D_CLIP_TEST_REGION); + mesh_foreachScreenEdge(vc, findnearestedge__doClosest, &data, V3D_PROJ_TEST_CLIP_WIN); - *dist = data.dist; + *r_dist = data.dist; return data.closest; } } -static void findnearestface__getDistance(void *userData, BMFace *efa, int x, int y, int UNUSED(index)) +static void findnearestface__getDistance(void *userData, BMFace *efa, const float screen_co[2], int UNUSED(index)) { - struct { short mval[2]; int dist; BMFace *toFace; } *data = userData; + struct { float mval_fl[2]; float dist; BMFace *toFace; } *data = userData; if (efa == data->toFace) { - int temp = abs(data->mval[0] - x) + abs(data->mval[1] - y); + const float dist_test = len_manhattan_v2v2(data->mval_fl, screen_co); - if (temp < data->dist) - data->dist = temp; + if (dist_test < data->dist) { + data->dist = dist_test; + } } } -static void findnearestface__doClosest(void *userData, BMFace *efa, int x, int y, int index) +static void findnearestface__doClosest(void *userData, BMFace *efa, const float screen_co[2], int index) { - struct { short mval[2], pass; int dist, lastIndex, closestIndex; BMFace *closest; } *data = userData; + struct { float mval_fl[2], pass; float dist, lastIndex, closestIndex; BMFace *closest; } *data = userData; if (data->pass == 0) { if (index <= data->lastIndex) @@ -563,17 +559,17 @@ static void findnearestface__doClosest(void *userData, BMFace *efa, int x, int y } if (data->dist > 3) { - int temp = abs(data->mval[0] - x) + abs(data->mval[1] - y); + const float dist_test = len_manhattan_v2v2(data->mval_fl, screen_co); - if (temp < data->dist) { - data->dist = temp; + if (dist_test < data->dist) { + data->dist = dist_test; data->closest = efa; data->closestIndex = index; } } } -BMFace *EDBM_face_find_nearest(ViewContext *vc, int *dist) +BMFace *EDBM_face_find_nearest(ViewContext *vc, float *r_dist) { if (vc->v3d->drawtype > OB_WIRE && (vc->v3d->flag & V3D_ZBUF_SELECT)) { @@ -586,17 +582,17 @@ BMFace *EDBM_face_find_nearest(ViewContext *vc, int *dist) efa = BM_face_at_index(vc->em->bm, index - 1); if (efa) { - struct { short mval[2]; int dist; BMFace *toFace; } data; + struct { float mval_fl[2]; float dist; BMFace *toFace; } data; - data.mval[0] = vc->mval[0]; - data.mval[1] = vc->mval[1]; + data.mval_fl[0] = vc->mval[0]; + data.mval_fl[1] = vc->mval[1]; data.dist = 0x7FFF; /* largest short */ data.toFace = efa; - mesh_foreachScreenFace(vc, findnearestface__getDistance, &data); + mesh_foreachScreenFace(vc, findnearestface__getDistance, &data, V3D_PROJ_TEST_CLIP_DEFAULT); - if (vc->em->selectmode == SCE_SELECT_FACE || data.dist < *dist) { /* only faces, no dist check */ - *dist = data.dist; + if ((vc->em->selectmode == SCE_SELECT_FACE) || (data.dist < *r_dist)) { /* only faces, no dist check */ + *r_dist = data.dist; return efa; } } @@ -604,7 +600,7 @@ BMFace *EDBM_face_find_nearest(ViewContext *vc, int *dist) return NULL; } else { - struct { short mval[2], pass; int dist, lastIndex, closestIndex; BMFace *closest; } data; + struct { float mval_fl[2], pass; float dist, lastIndex, closestIndex; BMFace *closest; } data; static int lastSelectedIndex = 0; static BMFace *lastSelected = NULL; @@ -614,23 +610,23 @@ BMFace *EDBM_face_find_nearest(ViewContext *vc, int *dist) } data.lastIndex = lastSelectedIndex; - data.mval[0] = vc->mval[0]; - data.mval[1] = vc->mval[1]; - data.dist = *dist; + data.mval_fl[0] = vc->mval[0]; + data.mval_fl[1] = vc->mval[1]; + data.dist = *r_dist; data.closest = NULL; data.closestIndex = 0; ED_view3d_init_mats_rv3d(vc->obedit, vc->rv3d); data.pass = 0; - mesh_foreachScreenFace(vc, findnearestface__doClosest, &data); + mesh_foreachScreenFace(vc, findnearestface__doClosest, &data, V3D_PROJ_TEST_CLIP_DEFAULT); - if (data.dist > 3) { + if (data.dist > 3.0f) { data.pass = 1; ED_view3d_init_mats_rv3d(vc->obedit, vc->rv3d); - mesh_foreachScreenFace(vc, findnearestface__doClosest, &data); + mesh_foreachScreenFace(vc, findnearestface__doClosest, &data, V3D_PROJ_TEST_CLIP_DEFAULT); } - *dist = data.dist; + *r_dist = data.dist; lastSelected = data.closest; lastSelectedIndex = data.closestIndex; @@ -646,7 +642,7 @@ BMFace *EDBM_face_find_nearest(ViewContext *vc, int *dist) static int unified_findnearest(ViewContext *vc, BMVert **r_eve, BMEdge **r_eed, BMFace **r_efa) { BMEditMesh *em = vc->em; - int dist = 75; + float dist = 75.0f; *r_eve = NULL; *r_eed = NULL; @@ -676,6 +672,13 @@ static int unified_findnearest(ViewContext *vc, BMVert **r_eve, BMEdge **r_eed, } /* **************** SIMILAR "group" SELECTS. FACE, EDGE AND VERTEX ************** */ +static EnumPropertyItem prop_similar_compare_types[] = { + {SIM_CMP_EQ, "EQUAL", 0, "Equal", ""}, + {SIM_CMP_GT, "GREATER", 0, "Greater", ""}, + {SIM_CMP_LT, "LESS", 0, "Less", ""}, + + {0, NULL, 0, NULL, NULL} +}; static EnumPropertyItem prop_similar_types[] = { {SIMVERT_NORMAL, "NORMAL", 0, "Normal", ""}, @@ -695,6 +698,7 @@ static EnumPropertyItem prop_similar_types[] = { {SIMFACE_MATERIAL, "MATERIAL", 0, "Material", ""}, {SIMFACE_IMAGE, "IMAGE", 0, "Image", ""}, {SIMFACE_AREA, "AREA", 0, "Area", ""}, + {SIMFACE_SIDES, "SIDES", 0, "Polygon Sides", ""}, {SIMFACE_PERIMETER, "PERIMETER", 0, "Perimeter", ""}, {SIMFACE_NORMAL, "NORMAL", 0, "Normal", ""}, {SIMFACE_COPLANAR, "COPLANAR", 0, "Co-planar", ""}, @@ -711,11 +715,14 @@ static int similar_face_select_exec(bContext *C, wmOperator *op) BMOperator bmop; /* get the type from RNA */ - int type = RNA_enum_get(op->ptr, "type"); - float thresh = RNA_float_get(op->ptr, "threshold"); + const int type = RNA_enum_get(op->ptr, "type"); + const float thresh = RNA_float_get(op->ptr, "threshold"); + const int compare = RNA_enum_get(op->ptr, "compare"); /* initialize the bmop using EDBM api, which does various ui error reporting and other stuff */ - EDBM_op_init(em, &bmop, op, "similar_faces faces=%hf type=%i thresh=%f", BM_ELEM_SELECT, type, thresh); + EDBM_op_init(em, &bmop, op, + "similar_faces faces=%hf type=%i thresh=%f compare=%i", + BM_ELEM_SELECT, type, thresh, compare); /* execute the operator */ BMO_op_exec(em->bm, &bmop); @@ -749,11 +756,14 @@ static int similar_edge_select_exec(bContext *C, wmOperator *op) BMOperator bmop; /* get the type from RNA */ - int type = RNA_enum_get(op->ptr, "type"); - float thresh = RNA_float_get(op->ptr, "threshold"); + const int type = RNA_enum_get(op->ptr, "type"); + const float thresh = RNA_float_get(op->ptr, "threshold"); + const int compare = RNA_enum_get(op->ptr, "compare"); /* initialize the bmop using EDBM api, which does various ui error reporting and other stuff */ - EDBM_op_init(em, &bmop, op, "similar_edges edges=%he type=%i thresh=%f", BM_ELEM_SELECT, type, thresh); + EDBM_op_init(em, &bmop, op, + "similar_edges edges=%he type=%i thresh=%f compare=%i", + BM_ELEM_SELECT, type, thresh, compare); /* execute the operator */ BMO_op_exec(em->bm, &bmop); @@ -790,11 +800,14 @@ static int similar_vert_select_exec(bContext *C, wmOperator *op) BMEditMesh *em = BMEdit_FromObject(ob); BMOperator bmop; /* get the type from RNA */ - int type = RNA_enum_get(op->ptr, "type"); + const int type = RNA_enum_get(op->ptr, "type"); float thresh = RNA_float_get(op->ptr, "threshold"); + const int compare = RNA_enum_get(op->ptr, "compare"); /* initialize the bmop using EDBM api, which does various ui error reporting and other stuff */ - EDBM_op_init(em, &bmop, op, "similar_verts verts=%hv type=%i thresh=%f", BM_ELEM_SELECT, type, thresh); + EDBM_op_init(em, &bmop, op, + "similar_verts verts=%hv type=%i thresh=%f compare=%i", + BM_ELEM_SELECT, type, thresh, compare); /* execute the operator */ BMO_op_exec(em->bm, &bmop); @@ -823,7 +836,7 @@ static int edbm_select_similar_exec(bContext *C, wmOperator *op) ToolSettings *ts = CTX_data_tool_settings(C); PropertyRNA *prop = RNA_struct_find_property(op->ptr, "threshold"); - int type = RNA_enum_get(op->ptr, "type"); + const int type = RNA_enum_get(op->ptr, "type"); if (!RNA_property_is_set(op->ptr, prop)) { RNA_property_float_set(op->ptr, prop, ts->select_thresh); @@ -834,7 +847,7 @@ static int edbm_select_similar_exec(bContext *C, wmOperator *op) if (type < 100) return similar_vert_select_exec(C, op); else if (type < 200) return similar_edge_select_exec(C, op); - else return similar_face_select_exec(C, op); + else return similar_face_select_exec(C, op); } static EnumPropertyItem *select_similar_type_itemf(bContext *C, PointerRNA *UNUSED(ptr), PropertyRNA *UNUSED(prop), @@ -898,7 +911,9 @@ void MESH_OT_select_similar(wmOperatorType *ot) prop = ot->prop = RNA_def_enum(ot->srna, "type", prop_similar_types, SIMVERT_NORMAL, "Type", ""); RNA_def_enum_funcs(prop, select_similar_type_itemf); - RNA_def_float(ot->srna, "threshold", 0.0, 0.0, 1.0, "Threshold", "", 0.01, 1.0); + RNA_def_enum(ot->srna, "compare", prop_similar_compare_types, SIM_CMP_EQ, "Compare", ""); + + RNA_def_float(ot->srna, "threshold", 0.0, 0.0, 1.0, "Threshold", "", 0.0, 1.0); } /* ***************************************************** */ @@ -1005,7 +1020,7 @@ static void mouse_mesh_loop(bContext *C, int mval[2], short extend, short ring) BMEditMesh *em; BMEdge *eed; int select = TRUE; - int dist = 50; + float dist = 50.0f; float mvalf[2]; em_setup_viewcontext(C, &vc); @@ -1060,11 +1075,11 @@ static void mouse_mesh_loop(bContext *C, int mval[2], short extend, short ring) /* We can't be sure this has already been set... */ ED_view3d_init_mats_rv3d(vc.obedit, vc.rv3d); - if (ED_view3d_project_float_object(vc.ar, eed->v1->co, v1_co, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_SUCCESS) { + if (ED_view3d_project_float_object(vc.ar, eed->v1->co, v1_co, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_OK) { length_1 = len_squared_v2v2(mvalf, v1_co); } - if (ED_view3d_project_float_object(vc.ar, eed->v2->co, v2_co, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_SUCCESS) { + if (ED_view3d_project_float_object(vc.ar, eed->v2->co, v2_co, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_OK) { length_2 = len_squared_v2v2(mvalf, v2_co); } #if 0 @@ -1091,7 +1106,7 @@ static void mouse_mesh_loop(bContext *C, int mval[2], short extend, short ring) float co[2], tdist; BM_face_calc_center_mean(f, cent); - if (ED_view3d_project_float_object(vc.ar, cent, co, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_SUCCESS) { + if (ED_view3d_project_float_object(vc.ar, cent, co, V3D_PROJ_TEST_NOP) == V3D_PROJ_RET_OK) { tdist = len_squared_v2v2(mvalf, co); if (tdist < best_dist) { /* printf("Best face: %p (%f)\n", f, tdist);*/ @@ -1161,19 +1176,17 @@ void MESH_OT_edgering_select(wmOperatorType *ot) RNA_def_boolean(ot->srna, "ring", 1, "Select Ring", "Select ring"); } -/* ******************* edgetag_shortest_path and helpers ****************** */ +/* ******************* generic tag_shortest_path and helpers ****************** */ -static float edgetag_cut_cost(BMEditMesh *UNUSED(em), BMEdge *e1, BMEdge *e2, BMVert *v) +static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3[3]) { - BMVert *v1 = (e1->v1 == v) ? e1->v2 : e1->v1; - BMVert *v2 = (e2->v1 == v) ? e2->v2 : e2->v1; float cost, d1[3], d2[3]; + /* The cost is based on the simple sum of the length of the two edgees... */ - sub_v3_v3v3(d1, v->co, v1->co); - sub_v3_v3v3(d2, v2->co, v->co); - cost = len_v3(d1); - cost += len_v3(d2); + sub_v3_v3v3(d1, v2, v1); + sub_v3_v3v3(d2, v3, v2); + cost = len_v3(d1) + len_v3(d2); /* but is biased to give higher values to sharp turns, so that it will take * paths with fewer "turns" when selecting between equal-weighted paths between @@ -1183,39 +1196,49 @@ static float edgetag_cut_cost(BMEditMesh *UNUSED(em), BMEdge *e1, BMEdge *e2, BM return cost; } -static void edgetag_add_adjacent(BMEditMesh *em, SmallHash *visithash, Heap *heap, int mednum, int vertnum, - int *nedges, int *edges, int *prevedge, float *cost) -{ - BMEdge *e1 = EDBM_edge_at_index(em, mednum); - BMVert *v = EDBM_vert_at_index(em, vertnum); - int startadj, endadj = nedges[vertnum + 1]; - - for (startadj = nedges[vertnum]; startadj < endadj; startadj++) { - int adjnum = edges[startadj]; - BMEdge *e2 = EDBM_edge_at_index(em, adjnum); - float newcost; - float cutcost; +/* ******************* edgetag_shortest_path and helpers ****************** */ - if (BLI_smallhash_haskey(visithash, (uintptr_t)e2)) - continue; +static float edgetag_cut_cost(BMEdge *e1, BMEdge *e2, BMVert *v) +{ + BMVert *v1 = BM_edge_other_vert(e1, v); + BMVert *v2 = BM_edge_other_vert(e2, v); + return step_cost_3_v3(v1->co, v->co, v2->co); +} - cutcost = edgetag_cut_cost(em, e1, e2, v); - newcost = cost[mednum] + cutcost; +static void edgetag_add_adjacent(Heap *heap, BMEdge *e1, BMEdge **edges_prev, float *cost) +{ + BMIter viter; + BMVert *v; - if (cost[adjnum] > newcost) { - cost[adjnum] = newcost; - prevedge[adjnum] = mednum; - BLI_heap_insert(heap, newcost, SET_INT_IN_POINTER(adjnum)); + BMIter eiter; + BMEdge *e2; + + const int e1_index = BM_elem_index_get(e1); + + BM_ITER_ELEM (v, &viter, e1, BM_VERTS_OF_EDGE) { + BM_ITER_ELEM (e2, &eiter, v, BM_EDGES_OF_VERT) { + if (!BM_elem_flag_test(e2, BM_ELEM_TAG)) { + /* we know 'e2' is not visited, check it out! */ + const int e2_index = BM_elem_index_get(e2); + const float cost_cut = edgetag_cut_cost(e1, e2, v); + const float cost_new = cost[e1_index] + cost_cut; + + if (cost[e2_index] > cost_new) { + cost[e2_index] = cost_new; + edges_prev[e2_index] = e1; + BLI_heap_insert(heap, cost_new, e2); + } + } } } } -static void edgetag_context_set(BMEditMesh *em, Scene *scene, BMEdge *e, int val) +static void edgetag_context_set(BMesh *bm, Scene *scene, BMEdge *e, int val) { switch (scene->toolsettings->edge_mode) { case EDGE_MODE_SELECT: - BM_edge_select_set(em->bm, e, val); + BM_edge_select_set(bm, e, val); break; case EDGE_MODE_TAG_SEAM: BM_elem_flag_set(e, BM_ELEM_SEAM, val); @@ -1224,98 +1247,66 @@ static void edgetag_context_set(BMEditMesh *em, Scene *scene, BMEdge *e, int val BM_elem_flag_set(e, BM_ELEM_SMOOTH, !val); break; case EDGE_MODE_TAG_CREASE: - { - float *crease = CustomData_bmesh_get(&em->bm->edata, e->head.data, CD_CREASE); - *crease = (val) ? 1.0f : 0.0f; + BM_elem_float_data_set(&bm->edata, e, CD_CREASE, (val) ? 1.0f : 0.0f); break; - } case EDGE_MODE_TAG_BEVEL: - { - float *bweight = CustomData_bmesh_get(&em->bm->edata, e->head.data, CD_BWEIGHT); - *bweight = (val) ? 1.0f : 0.0f; + BM_elem_float_data_set(&bm->edata, e, CD_BWEIGHT, (val) ? 1.0f : 0.0f); break; - } } } -static int edgetag_context_check(Scene *scene, BMEditMesh *em, BMEdge *e) +static int edgetag_context_check(Scene *scene, BMesh *bm, BMEdge *e) { switch (scene->toolsettings->edge_mode) { case EDGE_MODE_SELECT: - return BM_elem_flag_test(e, BM_ELEM_SELECT) ? 1 : 0; + return BM_elem_flag_test(e, BM_ELEM_SELECT) ? TRUE : FALSE; case EDGE_MODE_TAG_SEAM: return BM_elem_flag_test(e, BM_ELEM_SEAM); case EDGE_MODE_TAG_SHARP: return !BM_elem_flag_test(e, BM_ELEM_SMOOTH); case EDGE_MODE_TAG_CREASE: - return BM_elem_float_data_get(&em->bm->edata, e, CD_CREASE) ? 1 : 0; + return BM_elem_float_data_get(&bm->edata, e, CD_CREASE) ? TRUE : FALSE; case EDGE_MODE_TAG_BEVEL: - return BM_elem_float_data_get(&em->bm->edata, e, CD_BWEIGHT) ? 1 : 0; + return BM_elem_float_data_get(&bm->edata, e, CD_BWEIGHT) ? TRUE : FALSE; } return 0; } -static int edgetag_shortest_path(Scene *scene, BMEditMesh *em, BMEdge *source, BMEdge *target) +static int edgetag_shortest_path(Scene *scene, BMesh *bm, BMEdge *e_src, BMEdge *e_dst) { + /* BM_ELEM_TAG flag is used to store visited edges */ BMEdge *e; - BMIter iter; + BMIter eiter; Heap *heap; - SmallHash visithash; float *cost; - int i, totvert = 0, totedge = 0, *nedges, *edges, *prevedge, mednum = -1, nedgeswap = 0; - int targetnum; - - BLI_smallhash_init(&visithash); + BMEdge **edges_prev; + int i, totedge; /* note, would pass BM_EDGE except we are looping over all edges anyway */ - BM_mesh_elem_index_ensure(em->bm, BM_VERT /* | BM_EDGE */); + BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); - BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) { - if (BM_elem_flag_test(e, BM_ELEM_HIDDEN)) { - BLI_smallhash_insert(&visithash, (uintptr_t)e, NULL); + BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) { + if (BM_elem_flag_test(e, BM_ELEM_HIDDEN) == FALSE) { + BM_elem_flag_disable(e, BM_ELEM_TAG); + } + else { + BM_elem_flag_enable(e, BM_ELEM_TAG); } - BM_elem_index_set(e, totedge); /* set_inline */ - totedge++; + BM_elem_index_set(e, i); /* set_inline */ } - em->bm->elem_index_dirty &= ~BM_EDGE; + bm->elem_index_dirty &= ~BM_EDGE; /* alloc */ - totvert = em->bm->totvert; - nedges = MEM_callocN(sizeof(*nedges) * totvert + 1, "SeamPathNEdges"); - edges = MEM_mallocN(sizeof(*edges) * totedge * 2, "SeamPathEdges"); - prevedge = MEM_mallocN(sizeof(*prevedge) * totedge, "SeamPathPrevious"); + totedge = bm->totedge; + edges_prev = MEM_callocN(sizeof(*edges_prev) * totedge, "SeamPathPrevious"); cost = MEM_mallocN(sizeof(*cost) * totedge, "SeamPathCost"); - /* count edges, compute adjacent edges offsets and fill adjacent */ - BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) { - nedges[BM_elem_index_get(e->v1) + 1]++; - nedges[BM_elem_index_get(e->v2) + 1]++; - } - - for (i = 1; i < totvert; i++) { - int newswap = nedges[i + 1]; - nedges[i + 1] = nedgeswap + nedges[i]; - nedgeswap = newswap; - } - nedges[0] = nedges[1] = 0; - - i = 0; - BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) { - edges[nedges[BM_elem_index_get(e->v1) + 1]++] = i; - edges[nedges[BM_elem_index_get(e->v2) + 1]++] = i; - - cost[i] = 1e20f; - prevedge[i] = -1; - i++; - } + fill_vn_fl(cost, totedge, 1e20f); /* * Arrays are now filled as follows: * - * nedges[n] = sum of the # of edges incident to all vertices numbered 0 through n - 1 - * edges[edges[n]..edges[n - 1]] = the indices of of the edges incident to vertex n - * * As the search continues, prevedge[n] will be the previous edge on the shortest * path found so far to edge n. The visitedhash will of course contain entries * for edges that have been visited, cost[n] will contain the length of the shortest @@ -1326,61 +1317,46 @@ static int edgetag_shortest_path(Scene *scene, BMEditMesh *em, BMEdge *source, B /* regular dijkstra shortest path, but over edges instead of vertices */ heap = BLI_heap_new(); - BLI_heap_insert(heap, 0.0f, SET_INT_IN_POINTER(BM_elem_index_get(source))); - cost[BM_elem_index_get(source)] = 0.0f; - EDBM_index_arrays_init(em, 1, 1, 0); - targetnum = BM_elem_index_get(target); + BLI_heap_insert(heap, 0.0f, e_src); + cost[BM_elem_index_get(e_src)] = 0.0f; - while (!BLI_heap_empty(heap)) { - mednum = GET_INT_FROM_POINTER(BLI_heap_popmin(heap)); - e = EDBM_edge_at_index(em, mednum); + e = NULL; - if (mednum == targetnum) - break; - - if (BLI_smallhash_haskey(&visithash, (uintptr_t)e)) - continue; + while (!BLI_heap_is_empty(heap)) { + e = BLI_heap_popmin(heap); - BLI_smallhash_insert(&visithash, (uintptr_t)e, NULL); + if (e == e_dst) + break; - edgetag_add_adjacent(em, &visithash, heap, mednum, BM_elem_index_get(e->v1), nedges, edges, prevedge, cost); - edgetag_add_adjacent(em, &visithash, heap, mednum, BM_elem_index_get(e->v2), nedges, edges, prevedge, cost); + if (!BM_elem_flag_test(e, BM_ELEM_TAG)) { + BM_elem_flag_enable(e, BM_ELEM_TAG); + edgetag_add_adjacent(heap, e, edges_prev, cost); + } } - if (mednum == targetnum) { - short allseams = 1; + if (e == e_dst) { + short all_set = TRUE; /* Check whether the path is already completely tagged. * if it is, the tags will be cleared instead of set. */ - mednum = targetnum; + e = e_dst; do { - e = EDBM_edge_at_index(em, mednum); - if (!edgetag_context_check(scene, em, e)) { - allseams = 0; + if (!edgetag_context_check(scene, bm, e)) { + all_set = FALSE; break; } - mednum = prevedge[mednum]; - } while (mednum != BM_elem_index_get(source)); + } while ((e = edges_prev[BM_elem_index_get(e)])); /* Follow path back and source and add or remove tags */ - mednum = targetnum; + e = e_dst; do { - e = EDBM_edge_at_index(em, mednum); - if (allseams) - edgetag_context_set(em, scene, e, 0); - else - edgetag_context_set(em, scene, e, 1); - mednum = prevedge[mednum]; - } while (mednum != -1); + edgetag_context_set(bm, scene, e, !all_set); + } while ((e = edges_prev[BM_elem_index_get(e)])); } - EDBM_index_arrays_free(em); - MEM_freeN(nedges); - MEM_freeN(edges); - MEM_freeN(prevedge); + MEM_freeN(edges_prev); MEM_freeN(cost); BLI_heap_free(heap, NULL); - BLI_smallhash_release(&visithash); return 1; } @@ -1388,21 +1364,15 @@ static int edgetag_shortest_path(Scene *scene, BMEditMesh *em, BMEdge *source, B /* ******************* mesh shortest path select, uses prev-selected edge ****************** */ /* since you want to create paths with multiple selects, it doesn't have extend option */ -static int mouse_mesh_shortest_path(bContext *C, int mval[2]) +static int mouse_mesh_shortest_path_edge(bContext *C, ViewContext *vc) { - ViewContext vc; - BMEditMesh *em; - BMEdge *e; - int dist = 50; - - em_setup_viewcontext(C, &vc); - vc.mval[0] = mval[0]; - vc.mval[1] = mval[1]; - em = vc.em; + BMEditMesh *em = vc->em; + BMEdge *e_dst; + float dist = 75.0f; - e = EDBM_edge_find_nearest(&vc, &dist); - if (e) { - Mesh *me = vc.obedit->data; + e_dst = EDBM_edge_find_nearest(vc, &dist); + if (e_dst) { + Mesh *me = vc->obedit->data; int path = 0; if (em->bm->selected.last) { @@ -1411,8 +1381,8 @@ static int mouse_mesh_shortest_path(bContext *C, int mval[2]) if (ese && ese->htype == BM_EDGE) { BMEdge *e_act; e_act = (BMEdge *)ese->ele; - if (e_act != e) { - if (edgetag_shortest_path(vc.scene, em, e_act, e)) { + if (e_act != e_dst) { + if (edgetag_shortest_path(vc->scene, em->bm, e_act, e_dst)) { BM_select_history_remove(em->bm, e_act); path = 1; } @@ -1420,29 +1390,29 @@ static int mouse_mesh_shortest_path(bContext *C, int mval[2]) } } if (path == 0) { - int act = (edgetag_context_check(vc.scene, em, e) == 0); - edgetag_context_set(em, vc.scene, e, act); /* switch the edge option */ + int act = (edgetag_context_check(vc->scene, em->bm, e_dst) == 0); + edgetag_context_set(em->bm, vc->scene, e_dst, act); /* switch the edge option */ } EDBM_selectmode_flush(em); /* even if this is selected it may not be in the selection list */ - if (edgetag_context_check(vc.scene, em, e) == 0) - BM_select_history_remove(em->bm, e); + if (edgetag_context_check(vc->scene, em->bm, e_dst) == 0) + BM_select_history_remove(em->bm, e_dst); else - BM_select_history_store(em->bm, e); + BM_select_history_store(em->bm, e_dst); /* force drawmode for mesh */ switch (CTX_data_tool_settings(C)->edge_mode) { case EDGE_MODE_TAG_SEAM: me->drawflag |= ME_DRAWSEAMS; - ED_uvedit_live_unwrap(vc.scene, vc.obedit); + ED_uvedit_live_unwrap(vc->scene, vc->obedit); break; case EDGE_MODE_TAG_SHARP: me->drawflag |= ME_DRAWSHARP; break; - case EDGE_MODE_TAG_CREASE: + case EDGE_MODE_TAG_CREASE: me->drawflag |= ME_DRAWCREASES; break; case EDGE_MODE_TAG_BEVEL: @@ -1460,17 +1430,229 @@ static int mouse_mesh_shortest_path(bContext *C, int mval[2]) } +/* ******************* facetag_shortest_path and helpers ****************** */ + + +static float facetag_cut_cost(BMFace *f1, BMFace *f2, BMEdge *e) +{ + float f1_cent[3]; + float f2_cent[3]; + float e_cent[3]; + + BM_face_calc_center_mean(f1, f1_cent); + BM_face_calc_center_mean(f2, f2_cent); + mid_v3_v3v3(e_cent, e->v1->co, e->v2->co); + + return step_cost_3_v3(f1_cent, e_cent, f2_cent); +} + +static void facetag_add_adjacent(Heap *heap, BMFace *f1, BMFace **faces_prev, float *cost) +{ + BMIter liter; + BMLoop *l2; + BMFace *f2; + + const int f1_index = BM_elem_index_get(f1); + + /* loop over faces of face, but do so by first looping over loops */ + BM_ITER_ELEM (l2, &liter, f1, BM_LOOPS_OF_FACE) { + BMLoop *l_first; + BMLoop *l_iter; + + l_iter = l_first = l2; + do { + f2 = l_iter->f; + if (!BM_elem_flag_test(f2, BM_ELEM_TAG)) { + /* we know 'f2' is not visited, check it out! */ + const int f2_index = BM_elem_index_get(f2); + const float cost_cut = facetag_cut_cost(f1, f2, l_iter->e); + const float cost_new = cost[f1_index] + cost_cut; + + if (cost[f2_index] > cost_new) { + cost[f2_index] = cost_new; + faces_prev[f2_index] = f1; + BLI_heap_insert(heap, cost_new, f2); + } + } + } while ((l_iter = l_iter->radial_next) != l_first); + } +} + +static void facetag_context_set(BMesh *bm, Scene *UNUSED(scene), BMFace *f, int val) +{ + BM_face_select_set(bm, f, val); +} + +static int facetag_context_check(Scene *UNUSED(scene), BMesh *UNUSED(bm), BMFace *f) +{ + return BM_elem_flag_test(f, BM_ELEM_SELECT) ? 1 : 0; +} + +static int facetag_shortest_path(Scene *scene, BMesh *bm, BMFace *f_src, BMFace *f_dst) +{ + /* BM_ELEM_TAG flag is used to store visited edges */ + BMFace *f; + BMIter fiter; + Heap *heap; + float *cost; + BMFace **faces_prev; + int i, totface; + + /* note, would pass BM_EDGE except we are looping over all faces anyway */ + // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG + + BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) { + if (BM_elem_flag_test(f, BM_ELEM_HIDDEN) == FALSE) { + BM_elem_flag_disable(f, BM_ELEM_TAG); + } + else { + BM_elem_flag_enable(f, BM_ELEM_TAG); + } + + BM_elem_index_set(f, i); /* set_inline */ + } + bm->elem_index_dirty &= ~BM_FACE; + + /* alloc */ + totface = bm->totface; + faces_prev = MEM_callocN(sizeof(*faces_prev) * totface, "SeamPathPrevious"); + cost = MEM_mallocN(sizeof(*cost) * totface, "SeamPathCost"); + + fill_vn_fl(cost, totface, 1e20f); + + /* + * Arrays are now filled as follows: + * + * As the search continues, faces_prev[n] will be the previous face on the shortest + * path found so far to face n. The visitedhash will of course contain entries + * for faces that have been visited, cost[n] will contain the length of the shortest + * path to face n found so far, Finally, heap is a priority heap which is built on the + * the same data as the cost array, but inverted: it is a worklist of faces prioritized + * by the shortest path found so far to the face. + */ + + /* regular dijkstra shortest path, but over faces instead of vertices */ + heap = BLI_heap_new(); + BLI_heap_insert(heap, 0.0f, f_src); + cost[BM_elem_index_get(f_src)] = 0.0f; + + f = NULL; + + while (!BLI_heap_is_empty(heap)) { + f = BLI_heap_popmin(heap); + + if (f == f_dst) + break; + + if (!BM_elem_flag_test(f, BM_ELEM_TAG)) { + BM_elem_flag_enable(f, BM_ELEM_TAG); + facetag_add_adjacent(heap, f, faces_prev, cost); + } + } + + if (f == f_dst) { + short all_set = TRUE; + + /* Check whether the path is already completely tagged. + * if it is, the tags will be cleared instead of set. */ + f = f_dst; + do { + if (!facetag_context_check(scene, bm, f)) { + all_set = FALSE; + break; + } + } while ((f = faces_prev[BM_elem_index_get(f)])); + + /* Follow path back and source and add or remove tags */ + f = f_dst; + do { + facetag_context_set(bm, scene, f, !all_set); + } while ((f = faces_prev[BM_elem_index_get(f)])); + } + + MEM_freeN(faces_prev); + MEM_freeN(cost); + BLI_heap_free(heap, NULL); + + return 1; +} + +static int mouse_mesh_shortest_path_face(bContext *C, ViewContext *vc) +{ + BMEditMesh *em = vc->em; + BMFace *f_dst; + float dist = 75.0f; + + f_dst = EDBM_face_find_nearest(vc, &dist); + if (f_dst) { + int path = 0; + BMFace *f_act = BM_active_face_get(em->bm, FALSE, TRUE); + + if (f_act) { + if (f_act != f_dst) { + if (facetag_shortest_path(vc->scene, em->bm, f_act, f_dst)) { + BM_select_history_remove(em->bm, f_act); + path = 1; + } + } + } + if (path == 0) { + int act = (facetag_context_check(vc->scene, em->bm, f_dst) == 0); + facetag_context_set(em->bm, vc->scene, f_dst, act); /* switch the face option */ + } + + EDBM_selectmode_flush(em); + + /* even if this is selected it may not be in the selection list */ + if (facetag_context_check(vc->scene, em->bm, f_dst) == 0) + BM_select_history_remove(em->bm, f_dst); + else + BM_select_history_store(em->bm, f_dst); + + BM_active_face_set(em->bm, f_dst); + + EDBM_update_generic(C, em, FALSE); + + return TRUE; + } + else { + return FALSE; + } +} + + +/* ******************* operator for edge and face tag ****************** */ + static int edbm_shortest_path_select_invoke(bContext *C, wmOperator *UNUSED(op), wmEvent *event) { - + ViewContext vc; + BMEditMesh *em; + view3d_operator_needs_opengl(C); - if (mouse_mesh_shortest_path(C, event->mval)) { - return OPERATOR_FINISHED; + em_setup_viewcontext(C, &vc); + vc.mval[0] = event->mval[0]; + vc.mval[1] = event->mval[1]; + em = vc.em; + + if (em->selectmode & SCE_SELECT_EDGE) { + if (mouse_mesh_shortest_path_edge(C, &vc)) { + return OPERATOR_FINISHED; + } + else { + return OPERATOR_PASS_THROUGH; + } } - else { - return OPERATOR_PASS_THROUGH; + else if (em->selectmode & SCE_SELECT_FACE) { + if (mouse_mesh_shortest_path_face(C, &vc)) { + return OPERATOR_FINISHED; + } + else { + return OPERATOR_PASS_THROUGH; + } } + + return OPERATOR_PASS_THROUGH; } static int edbm_shortest_path_select_poll(bContext *C) @@ -1478,7 +1660,7 @@ static int edbm_shortest_path_select_poll(bContext *C) if (ED_operator_editmesh_region_view3d(C)) { Object *obedit = CTX_data_edit_object(C); BMEditMesh *em = BMEdit_FromObject(obedit); - return (em->selectmode & SCE_SELECT_EDGE) != 0; + return (em->selectmode & (SCE_SELECT_EDGE | SCE_SELECT_FACE)) != 0; } return 0; } @@ -1712,7 +1894,7 @@ void EDBM_selectmode_convert(BMEditMesh *em, short selectmode_old, short selectm BM_edge_select_set(em->bm, eed, TRUE); } } - } + } else if (selectmode_new == SCE_SELECT_FACE) { BMIter liter; BMLoop *l; @@ -2170,11 +2352,19 @@ static void walker_deselect_nth(BMEditMesh *em, int nth, int offset, BMHeader *h BMW_FLAG_NOP, /* don't use BMW_FLAG_TEST_HIDDEN here since we want to desel all */ BMW_NIL_LAY); + /* use tag to avoid touching the same verts twice */ + BM_ITER_MESH (ele, &iter, bm, itertype) { + BM_elem_flag_disable(ele, BM_ELEM_TAG); + } + BLI_assert(walker.order == BMW_BREADTH_FIRST); for (ele = BMW_begin(&walker, h_act); ele != NULL; ele = BMW_step(&walker)) { - /* Deselect elements that aren't at "nth" depth from active */ - if ((offset + BMW_current_depth(&walker)) % nth) { - BM_elem_select_set(bm, ele, FALSE); + if (!BM_elem_flag_test(ele, BM_ELEM_TAG)) { + /* Deselect elements that aren't at "nth" depth from active */ + if ((offset + BMW_current_depth(&walker)) % nth) { + BM_elem_select_set(bm, ele, FALSE); + } + BM_elem_flag_enable(ele, BM_ELEM_TAG); } } BMW_end(&walker); @@ -2286,9 +2476,9 @@ static int edbm_select_nth_exec(bContext *C, wmOperator *op) void MESH_OT_select_nth(wmOperatorType *ot) { /* identifiers */ - ot->name = "Select Nth"; + ot->name = "Checker Deselect"; ot->idname = "MESH_OT_select_nth"; - ot->description = "Select every Nth element starting from a selected vertex, edge or face"; + ot->description = "Deselect every Nth element starting from a selected vertex, edge or face"; /* api callbacks */ ot->exec = edbm_select_nth_exec; @@ -2297,8 +2487,8 @@ void MESH_OT_select_nth(wmOperatorType *ot) /* flags */ ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO; - RNA_def_int(ot->srna, "nth", 2, 2, 100, "Nth Selection", "", 1, INT_MAX); - RNA_def_int(ot->srna, "offset", 0, 0, 100, "Offset", "", 0, INT_MAX); + RNA_def_int(ot->srna, "nth", 2, 2, INT_MAX, "Nth Selection", "", 2, 100); + RNA_def_int(ot->srna, "offset", 0, 0, INT_MAX, "Offset", "", 0, 100); } void em_setup_viewcontext(bContext *C, ViewContext *vc) @@ -2469,7 +2659,7 @@ static int edbm_select_non_manifold_exec(bContext *C, wmOperator *op) */ if (em->selectmode == SCE_SELECT_FACE) { - BKE_report(op->reports, RPT_ERROR, "Doesn't work in face selection mode"); + BKE_report(op->reports, RPT_ERROR, "Does not work in face selection mode"); return OPERATOR_CANCELLED; } |