[Bf-blender-cvs] [cdbb60b] master: Select Shortest Path for edit-curve
Campbell Barton
noreply at git.blender.org
Thu Jul 9 09:08:29 CEST 2015
Commit: cdbb60b0a38fa54d58b9ebcf29bd060c0f1b885c
Author: Campbell Barton
Date: Thu Jul 9 13:14:09 2015 +1000
Branches: master
https://developer.blender.org/rBcdbb60b0a38fa54d58b9ebcf29bd060c0f1b885c
Select Shortest Path for edit-curve
D1391 by @pink.vertex with own fixes/edits
===================================================================
M source/blender/blenkernel/BKE_curve.h
M source/blender/blenkernel/intern/curve.c
M source/blender/editors/curve/curve_intern.h
M source/blender/editors/curve/curve_ops.c
M source/blender/editors/curve/editcurve_select.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_curve.h b/source/blender/blenkernel/BKE_curve.h
index 20b66a5..a03dd28 100644
--- a/source/blender/blenkernel/BKE_curve.h
+++ b/source/blender/blenkernel/BKE_curve.h
@@ -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);
diff --git a/source/blender/blenkernel/intern/curve.c b/source/blender/blenkernel/intern/curve.c
index d8a7b2d..e769b4f 100644
--- a/source/blender/blenkernel/intern/curve.c
+++ b/source/blender/blenkernel/intern/curve.c
@@ -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;
diff --git a/source/blender/editors/curve/curve_intern.h b/source/blender/editors/curve/curve_intern.h
index 86d7c4e..29904bf 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 64ca446..4828fb3 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 680fda3..ef7097d 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) {
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list