Select Shortest Path for edit-curve
authorCampbell Barton <ideasman42@gmail.com>
Thu, 9 Jul 2015 03:14:09 +0000 (13:14 +1000)
committerCampbell Barton <ideasman42@gmail.com>
Thu, 9 Jul 2015 07:03:00 +0000 (17:03 +1000)
D1391 by @pink.vertex with own fixes/edits

source/blender/blenkernel/BKE_curve.h
source/blender/blenkernel/intern/curve.c
source/blender/editors/curve/curve_intern.h
source/blender/editors/curve/curve_ops.c
source/blender/editors/curve/editcurve_select.c

index 20b66a59b12a77b6209a78757b279e1a55bbf48b..a03dd2871467d0d617971c215bb67f9e8e4dcb4d 100644 (file)
@@ -94,10 +94,11 @@ void BKE_curve_material_remap(struct Curve *cu, const unsigned int *remap, unsig
 
 ListBase    *BKE_curve_nurbs_get(struct Curve *cu);
 
-void         BKE_curve_nurb_active_set(struct Curve *cu, struct Nurb *nu);
+int          BKE_curve_nurb_vert_index_get(const struct Nurb *nu, const void *vert);
+void         BKE_curve_nurb_active_set(struct Curve *cu, const struct Nurb *nu);
 struct Nurb *BKE_curve_nurb_active_get(struct Curve *cu);
 void        *BKE_curve_vert_active_get(struct Curve *cu);
-void         BKE_curve_nurb_vert_active_set(struct Curve *cu, struct Nurb *nu,    void *vert);
+void         BKE_curve_nurb_vert_active_set(struct Curve *cu, const struct Nurb *nu, const void *vert);
 bool         BKE_curve_nurb_vert_active_get(struct Curve *cu, struct Nurb **r_nu, void **r_vert);
 void         BKE_curve_nurb_vert_active_validate(struct Curve *cu);
 
@@ -166,6 +167,9 @@ bool BKE_nurb_type_convert(struct Nurb *nu, const short type, const bool use_han
 void BKE_nurb_points_add(struct Nurb *nu, int number);
 void BKE_nurb_bezierPoints_add(struct Nurb *nu, int number);
 
+int  BKE_nurb_index_from_uv(struct Nurb *nu, int u, int v);
+void BKE_nurb_index_to_uv(struct Nurb *nu, int index, int *r_u, int *r_v);
+
 struct BezTriple *BKE_nurb_bezt_get_next(struct Nurb *nu, struct BezTriple *bezt);
 struct BezTriple *BKE_nurb_bezt_get_prev(struct Nurb *nu, struct BezTriple *bezt);
 struct BPoint    *BKE_nurb_bpoint_get_next(struct Nurb *nu, struct BPoint *bp);
index d8a7b2d3d0684ca01cec21971306e4a3a81893e1..e769b4fce97109c9afba39d1cbac09867b801c75 100644 (file)
@@ -737,6 +737,41 @@ void BKE_nurb_bezierPoints_add(Nurb *nu, int number)
 }
 
 
+int BKE_nurb_index_from_uv(
+        Nurb *nu,
+        int u, int v)
+{
+       const int totu = nu->pntsu;
+       const int totv = nu->pntsv;
+
+       if (nu->flagu & CU_NURB_CYCLIC) {
+               u = mod_i(u, totu);
+       }
+       else if (u < 0 || u >= totu) {
+               return -1;
+       }
+
+       if (nu->flagv & CU_NURB_CYCLIC) {
+               v = mod_i(v, totv);
+       }
+       else if (v < 0 || v >= totv) {
+               return -1;
+       }
+
+       return (v * totu) + u;
+}
+
+void BKE_nurb_index_to_uv(
+        Nurb *nu, int index,
+        int *r_u, int *r_v)
+{
+       const int totu = nu->pntsu;
+       const int totv = nu->pntsv;
+       BLI_assert(index >= 0 && index < (nu->pntsu * nu->pntsv));
+       *r_u = (index % totu);
+       *r_v = (index / totu) % totv;
+}
+
 BezTriple *BKE_nurb_bezt_get_next(Nurb *nu, BezTriple *bezt)
 {
        BezTriple *bezt_next;
@@ -4204,7 +4239,7 @@ ListBase *BKE_curve_nurbs_get(Curve *cu)
        return &cu->nurb;
 }
 
-void BKE_curve_nurb_active_set(Curve *cu, Nurb *nu)
+void BKE_curve_nurb_active_set(Curve *cu, const Nurb *nu)
 {
        if (nu == NULL) {
                cu->actnu = CU_ACT_NONE;
@@ -4231,21 +4266,26 @@ void *BKE_curve_vert_active_get(Curve *cu)
        return vert;
 }
 
+int BKE_curve_nurb_vert_index_get(const Nurb *nu, const void *vert)
+{
+       if (nu->type == CU_BEZIER) {
+               BLI_assert(ARRAY_HAS_ITEM((BezTriple *)vert, nu->bezt, nu->pntsu));
+               return (BezTriple *)vert - nu->bezt;
+       }
+       else {
+               BLI_assert(ARRAY_HAS_ITEM((BPoint *)vert, nu->bp, nu->pntsu * nu->pntsv));
+               return (BPoint *)vert - nu->bp;
+       }
+}
+
 /* Set active nurb and active vert for curve */
-void BKE_curve_nurb_vert_active_set(Curve *cu, Nurb *nu, void *vert)
+void BKE_curve_nurb_vert_active_set(Curve *cu, const Nurb *nu, const void *vert)
 {
        if (nu) {
                BKE_curve_nurb_active_set(cu, nu);
 
                if (vert) {
-                       if (nu->type == CU_BEZIER) {
-                               BLI_assert(ARRAY_HAS_ITEM((BezTriple *)vert, nu->bezt, nu->pntsu));
-                               cu->actvert = (BezTriple *)vert - nu->bezt;
-                       }
-                       else {
-                               BLI_assert(ARRAY_HAS_ITEM((BPoint *)vert, nu->bp, nu->pntsu * nu->pntsv));
-                               cu->actvert = (BPoint *)vert - nu->bp;
-                       }
+                       cu->actvert = BKE_curve_nurb_vert_index_get(nu, vert);
                }
                else {
                        cu->actvert = CU_ACT_NONE;
index 86d7c4e8cb987226864907735ede5f5ddd7e4142..29904bf23447a00367e2b51a6ebc70dd8626d6e5 100644 (file)
@@ -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);
index 64ca4466b6f6e07b0e3e4d7778718cb4f40ccee9..4828fb3ec5f22c149d7299b0eb6b944ad6065671 100644 (file)
@@ -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);
index 680fda35f2bed6079dfa0ba394fa433b4582c723..ef7097deb4c599c91856c42860f02da82d06bd87 100644 (file)
@@ -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