From cdbb60b0a38fa54d58b9ebcf29bd060c0f1b885c Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Thu, 9 Jul 2015 13:14:09 +1000 Subject: Select Shortest Path for edit-curve D1391 by @pink.vertex with own fixes/edits --- source/blender/editors/curve/curve_intern.h | 1 + source/blender/editors/curve/curve_ops.c | 3 + source/blender/editors/curve/editcurve_select.c | 232 +++++++++++++++++++++++- 3 files changed, 235 insertions(+), 1 deletion(-) (limited to 'source/blender/editors/curve') diff --git a/source/blender/editors/curve/curve_intern.h b/source/blender/editors/curve/curve_intern.h index 86d7c4e8cb9..29904bf2344 100644 --- a/source/blender/editors/curve/curve_intern.h +++ b/source/blender/editors/curve/curve_intern.h @@ -151,6 +151,7 @@ void CURVE_OT_select_less(struct wmOperatorType *ot); void CURVE_OT_select_random(struct wmOperatorType *ot); void CURVE_OT_select_nth(struct wmOperatorType *ot); void CURVE_OT_select_similar(struct wmOperatorType *ot); +void CURVE_OT_shortest_path_pick(struct wmOperatorType *ot); /* editcurve_add.c */ void CURVE_OT_primitive_bezier_curve_add(struct wmOperatorType *ot); diff --git a/source/blender/editors/curve/curve_ops.c b/source/blender/editors/curve/curve_ops.c index 64ca4466b6f..4828fb3ec5f 100644 --- a/source/blender/editors/curve/curve_ops.c +++ b/source/blender/editors/curve/curve_ops.c @@ -129,6 +129,7 @@ void ED_operatortypes_curve(void) WM_operatortype_append(CURVE_OT_select_random); WM_operatortype_append(CURVE_OT_select_nth); WM_operatortype_append(CURVE_OT_select_similar); + WM_operatortype_append(CURVE_OT_shortest_path_pick); WM_operatortype_append(CURVE_OT_switch_direction); WM_operatortype_append(CURVE_OT_subdivide); @@ -249,6 +250,8 @@ void ED_keymap_curve(wmKeyConfig *keyconf) kmi = WM_keymap_add_item(keymap, "CURVE_OT_select_linked_pick", LKEY, KM_PRESS, KM_SHIFT, 0); RNA_boolean_set(kmi->ptr, "deselect", true); + WM_keymap_add_item(keymap, "CURVE_OT_shortest_path_pick", SELECTMOUSE, KM_CLICK, KM_CTRL, 0); + WM_keymap_add_item(keymap, "CURVE_OT_separate", PKEY, KM_PRESS, 0, 0); WM_keymap_add_item(keymap, "CURVE_OT_split", YKEY, KM_PRESS, 0, 0); WM_keymap_add_item(keymap, "CURVE_OT_extrude_move", EKEY, KM_PRESS, 0, 0); diff --git a/source/blender/editors/curve/editcurve_select.c b/source/blender/editors/curve/editcurve_select.c index 680fda35f2b..ef7097deb4c 100644 --- a/source/blender/editors/curve/editcurve_select.c +++ b/source/blender/editors/curve/editcurve_select.c @@ -37,7 +37,7 @@ #include "BLI_bitmap.h" #include "BLI_math.h" #include "BLI_rand.h" - +#include "BLI_heap.h" #include "BKE_context.h" #include "BKE_curve.h" @@ -1496,3 +1496,233 @@ void CURVE_OT_select_similar(wmOperatorType *ot) } /** \} */ + + +/* -------------------------------------------------------------------- */ +/* Select Shortest Path */ + +/** \name Select Path + * \{ */ + +static float curve_calc_dist_pair(const Nurb *nu, int a, int b) +{ + const float *a_fl, *b_fl; + + if (nu->type == CU_BEZIER) { + a_fl = nu->bezt[a].vec[1]; + b_fl = nu->bezt[b].vec[1]; + } + else { + a_fl = nu->bp[a].vec; + b_fl = nu->bp[b].vec; + } + + return len_v3v3(a_fl, b_fl); +} + +static float curve_calc_dist_span(Nurb *nu, int vert_src, int vert_dst) +{ + const int u = nu->pntsu; + int i_prev, i; + float dist = 0.0f; + + BLI_assert(nu->pntsv == 1); + + i_prev = vert_src; + i = (i_prev + 1) % u; + + while (true) { + dist += curve_calc_dist_pair(nu, i_prev, i); + + if (i == vert_dst) { + break; + } + i = (i + 1) % u; + } + return dist; +} + +static void curve_select_shortest_path_curve(Nurb *nu, int vert_src, int vert_dst) +{ + const int u = nu->pntsu; + int i; + + if (vert_src > vert_dst) { + SWAP(int, vert_src, vert_dst); + } + + if (nu->flagu & CU_NURB_CYCLIC) { + if (curve_calc_dist_span(nu, vert_src, vert_dst) > + curve_calc_dist_span(nu, vert_dst, vert_src)) + { + SWAP(int, vert_src, vert_dst); + } + } + + i = vert_src; + while (true) { + if (nu->type & CU_BEZIER) { + select_beztriple(&nu->bezt[i], SELECT, SELECT, HIDDEN); + } + else { + select_bpoint(&nu->bp[i], SELECT, SELECT, HIDDEN); + } + + if (i == vert_dst) { + break; + } + i = (i + 1) % u; + } +} + +static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst) +{ + Heap *heap; + + int i, vert_curr; + + int totu = nu->pntsu; + int totv = nu->pntsv; + int vert_num = totu * totv; + + /* custom data */ + struct PointAdj { + int vert, vert_prev; + float cost; + } *data; + + /* init connectivity data */ + data = MEM_mallocN(sizeof(*data) * vert_num, __func__); + for (i = 0; i < vert_num; i++) { + data[i].vert = i; + data[i].vert_prev = -1; + data[i].cost = FLT_MAX; + } + + /* init heap */ + heap = BLI_heap_new(); + + BLI_heap_insert(heap, 0.0f, &data[vert_src].vert); + data[vert_src].cost = 0.0f; + data[vert_src].vert_prev = vert_src; /* nop */ + + while (!BLI_heap_is_empty(heap)) { + int axis, sign; + int u, v; + + vert_curr = *((int *)BLI_heap_popmin(heap)); + if (vert_curr == vert_dst) { + break; + } + + BKE_nurb_index_to_uv(nu, vert_curr, &u, &v); + + /* loop over 4 adjacent verts */ + for (sign = -1; sign != 3; sign += 2) { + for (axis = 0; axis != 2; axis += 1) { + int uv_other[2] = {u, v}; + int vert_other; + + uv_other[axis] += sign; + + vert_other = BKE_nurb_index_from_uv(nu, uv_other[0], uv_other[1]); + if (vert_other != -1) { + const float dist = data[vert_curr].cost + curve_calc_dist_pair(nu, vert_curr, vert_other); + + if (data[vert_other].cost > dist) { + data[vert_other].cost = dist; + if (data[vert_other].vert_prev == -1) { + BLI_heap_insert(heap, data[vert_other].cost, &data[vert_other].vert); + } + data[vert_other].vert_prev = vert_curr; + } + } + + } + } + + } + + BLI_heap_free(heap, NULL); + + if (vert_curr == vert_dst) { + i = 0; + while (vert_curr != vert_src && i++ < vert_num) { + if (nu->type == CU_BEZIER) { + select_beztriple(&nu->bezt[vert_curr], SELECT, SELECT, HIDDEN); + } + else { + select_bpoint(&nu->bp[vert_curr], SELECT, SELECT, HIDDEN); + } + vert_curr = data[vert_curr].vert_prev; + } + } + + MEM_freeN(data); +} + +static int edcu_shortest_path_pick_invoke(bContext *C, wmOperator *op, const wmEvent *event) +{ + Object *obedit = CTX_data_edit_object(C); + Curve *cu = obedit->data; + Nurb *nu_src = BKE_curve_nurb_active_get(cu); + int vert_src = cu->actvert; + + ViewContext vc; + Nurb *nu_dst; + BezTriple *bezt_dst; + BPoint *bp_dst; + int vert_dst; + void *vert_dst_p; + + if (vert_src == CU_ACT_NONE) { + return OPERATOR_PASS_THROUGH; + } + + view3d_operator_needs_opengl(C); + view3d_set_viewcontext(C, &vc); + + if (!ED_curve_pick_vert(&vc, 1, event->mval, &nu_dst, &bezt_dst, &bp_dst, NULL)) { + return OPERATOR_PASS_THROUGH; + } + + if (nu_src != nu_dst) { + BKE_report(op->reports, RPT_ERROR, "Control point belongs to another spline"); + return OPERATOR_CANCELLED; + } + + vert_dst_p = bezt_dst ? (void *)bezt_dst : (void *)bp_dst; + vert_dst = BKE_curve_nurb_vert_index_get(nu_dst, vert_dst_p); + if (vert_src == vert_dst) { + return OPERATOR_CANCELLED; + } + + if ((obedit->type == OB_SURF) && (nu_src->pntsv > 1)) { + curve_select_shortest_path_surf(nu_src, vert_src, vert_dst); + } + else { + curve_select_shortest_path_curve(nu_src, vert_src, vert_dst); + } + + BKE_curve_nurb_vert_active_set(cu, nu_dst, vert_dst_p); + + WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data); + return OPERATOR_FINISHED; +} + +void CURVE_OT_shortest_path_pick(wmOperatorType *ot) +{ + /* identifiers */ + ot->name = "Pick Shortest Path"; + ot->idname = "CURVE_OT_shortest_path_pick"; + ot->description = "Select shortest path between two selections"; + + /* api callbacks */ + ot->invoke = edcu_shortest_path_pick_invoke; + ot->poll = ED_operator_editsurfcurve_region_view3d; + + /* flags */ + ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO; +} + +/** \} */ \ No newline at end of file -- cgit v1.2.3