Armature Editing: select shortest path (Ctrl+RMB matching mesh operator)

Patch originally from Terry Struven, modified to use more generic functions.

5 files changed, 166 insertions, 0 deletions

diff --git a/source/blender/editors/armature/armature_intern.h b/source/blender/editors/armature/armature_intern.h
index bc7d69d1558..f3db9042879 100644
--- a/source/blender/editors/armature/armature_intern.h
+++ b/source/blender/editors/armature/armature_intern.h
@@ -68,6 +68,7 @@ void ARMATURE_OT_select_less(struct wmOperatorType *ot);
 void ARMATURE_OT_select_hierarchy(struct wmOperatorType *ot);
 void ARMATURE_OT_select_linked(struct wmOperatorType *ot);
 void ARMATURE_OT_select_similar(struct wmOperatorType *ot);
+void ARMATURE_OT_shortest_path_pick(struct wmOperatorType *ot);
 
 void ARMATURE_OT_delete(struct wmOperatorType *ot);
 void ARMATURE_OT_duplicate(struct wmOperatorType *ot);
diff --git a/source/blender/editors/armature/armature_ops.c b/source/blender/editors/armature/armature_ops.c
index 4c7eb847054..feb9b0f939a 100644
--- a/source/blender/editors/armature/armature_ops.c
+++ b/source/blender/editors/armature/armature_ops.c
@@ -64,6 +64,7 @@ void ED_operatortypes_armature(void)
 	WM_operatortype_append(ARMATURE_OT_select_hierarchy);
 	WM_operatortype_append(ARMATURE_OT_select_linked);
 	WM_operatortype_append(ARMATURE_OT_select_similar);
+	WM_operatortype_append(ARMATURE_OT_shortest_path_pick);
 
 	WM_operatortype_append(ARMATURE_OT_delete);
 	WM_operatortype_append(ARMATURE_OT_duplicate);
@@ -264,6 +265,8 @@ void ED_keymap_armature(wmKeyConfig *keyconf)
 	WM_keymap_add_item(keymap, "ARMATURE_OT_select_similar", GKEY, KM_PRESS, KM_SHIFT, 0);
 
 	WM_keymap_add_item(keymap, "ARMATURE_OT_select_linked", LKEY, KM_PRESS, 0, 0);
+
+	WM_keymap_add_item(keymap, "ARMATURE_OT_shortest_path_pick", SELECTMOUSE, KM_PRESS, KM_CTRL, 0);
 	
 	WM_keymap_add_item(keymap, "ARMATURE_OT_delete", XKEY, KM_PRESS, 0, 0);
 	WM_keymap_add_item(keymap, "ARMATURE_OT_delete", DELKEY, KM_PRESS, 0, 0);
diff --git a/source/blender/editors/armature/armature_select.c b/source/blender/editors/armature/armature_select.c
index 003f6bf36f3..0bc6f1e037c 100644
--- a/source/blender/editors/armature/armature_select.c
+++ b/source/blender/editors/armature/armature_select.c
@@ -1120,3 +1120,123 @@ void ARMATURE_OT_select_mirror(wmOperatorType *ot)
 	RNA_def_boolean(ot->srna, "only_active", false, "Active Only", "Only operate on the active bone");
 	RNA_def_boolean(ot->srna, "extend", false, "Extend", "Extend the selection");
 }
+
+
+/****************** Select Path ****************/
+
+static bool armature_shortest_path_select(bArmature *arm, EditBone *ebone_parent, EditBone *ebone_child,
+                                          bool use_parent, bool is_test)
+{
+	do {
+
+		if (!use_parent && (ebone_child == ebone_parent))
+			break;
+
+		if (is_test) {
+			if (!EBONE_SELECTABLE(arm, ebone_child)) {
+				return false;
+			}
+		}
+		else {
+			ED_armature_ebone_selectflag_set(ebone_child, (BONE_SELECTED | BONE_TIPSEL | BONE_ROOTSEL));
+		}
+
+		if (ebone_child == ebone_parent)
+			break;
+
+		ebone_child = ebone_child->parent;
+	} while (true);
+
+	return true;
+}
+
+static int armature_shortest_path_pick_invoke(bContext *C, wmOperator *op, const wmEvent *event)
+{
+	Object *obedit = CTX_data_edit_object(C);
+	bArmature *arm = obedit->data;
+	EditBone *ebone_src, *ebone_dst;
+	EditBone *ebone_isect_parent = NULL;
+	EditBone *ebone_isect_child[2];
+	bool change;
+
+	view3d_operator_needs_opengl(C);
+
+	ebone_src = arm->act_edbone;
+	ebone_dst = get_nearest_bone(C, 0, event->mval[0], event->mval[1]);
+
+	/* fallback to object selection */
+	if (ELEM(NULL, ebone_src, ebone_dst) || (ebone_src == ebone_dst)) {
+		return OPERATOR_PASS_THROUGH;
+	}
+
+	ebone_isect_child[0] = ebone_src;
+	ebone_isect_child[1] = ebone_dst;
+
+
+	/* ensure 'ebone_src' is the parent of 'ebone_dst', or set 'ebone_isect_parent' */
+	if (ED_armature_ebone_is_child_recursive(ebone_src, ebone_dst)) {
+		/* pass */
+	}
+	else if (ED_armature_ebone_is_child_recursive(ebone_dst, ebone_src)) {
+		SWAP(EditBone *, ebone_src, ebone_dst);
+	}
+	else if ((ebone_isect_parent = ED_armature_bone_find_shared_parent(ebone_isect_child, 2))) {
+		/* pass */
+	}
+	else {
+		/* disconnected bones */
+		return OPERATOR_CANCELLED;
+	}
+
+
+	if (ebone_isect_parent) {
+		if (armature_shortest_path_select(arm, ebone_isect_parent, ebone_src, false, true) &&
+		    armature_shortest_path_select(arm, ebone_isect_parent, ebone_dst, false, true))
+		{
+			armature_shortest_path_select(arm, ebone_isect_parent, ebone_src, false, false);
+			armature_shortest_path_select(arm, ebone_isect_parent, ebone_dst, false, false);
+			change = true;
+		}
+		else {
+			/* unselectable */
+			change = false;
+		}
+	}
+	else {
+		if (armature_shortest_path_select(arm, ebone_src, ebone_dst, true, true)) {
+			armature_shortest_path_select(arm, ebone_src, ebone_dst, true, false);
+			change = true;
+		}
+		else {
+			/* unselectable */
+			change = false;
+		}
+	}
+
+	if (change) {
+		arm->act_edbone = ebone_dst;
+		ED_armature_sync_selection(arm->edbo);
+		WM_event_add_notifier(C, NC_OBJECT | ND_BONE_SELECT, obedit);
+
+		return OPERATOR_FINISHED;
+	}
+	else {
+		BKE_report(op->reports, RPT_WARNING, "Unselectable bone in chain");
+		return OPERATOR_CANCELLED;
+	}
+}
+
+void ARMATURE_OT_shortest_path_pick(wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name = "Pick Shortest Path";
+	ot->idname = "ARMATURE_OT_shortest_path_pick";
+	ot->description = "Select shortest path between two bones";
+
+	/* api callbacks */
+	ot->invoke = armature_shortest_path_pick_invoke;
+	ot->poll = ED_operator_editarmature;
+
+	/* flags */
+	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
+}
diff --git a/source/blender/editors/armature/armature_utils.c b/source/blender/editors/armature/armature_utils.c
index 2cbfb52db91..be26ad537fc 100644
--- a/source/blender/editors/armature/armature_utils.c
+++ b/source/blender/editors/armature/armature_utils.c
@@ -156,6 +156,47 @@ bool ED_armature_ebone_is_child_recursive(EditBone *ebone_parent, EditBone *ebon
 	return false;
 }
 
+/**
+ * Finds the first parent shared by \a ebone_child
+ *
+ * \param ebone_child  Children bones to search
+ * \param ebone_child_tot  Size of the ebone_child array
+ * \return The shared parent or NULL.
+ */
+EditBone *ED_armature_bone_find_shared_parent(EditBone *ebone_child[], const unsigned int ebone_child_tot)
+{
+	unsigned int i;
+	EditBone *ebone_iter;
+
+#define EBONE_TEMP_UINT(ebone) (*((unsigned int *)(&((ebone)->temp))))
+
+	/* clear all */
+	for (i = 0; i < ebone_child_tot; i++) {
+		for (ebone_iter = ebone_child[i]; ebone_iter; ebone_iter = ebone_iter->parent) {
+			EBONE_TEMP_UINT(ebone_iter) = 0;
+		}
+	}
+
+	/* accumulate */
+	for (i = 0; i < ebone_child_tot; i++) {
+		ebone_iter = ebone_child[i];
+		for (ebone_iter = ebone_child[i]->parent; ebone_iter; ebone_iter = ebone_iter->parent) {
+			EBONE_TEMP_UINT(ebone_iter) += 1;
+		}
+	}
+
+	/* only need search the first chain */
+	for (ebone_iter = ebone_child[0]->parent; ebone_iter; ebone_iter = ebone_iter->parent) {
+		if (EBONE_TEMP_UINT(ebone_iter) == ebone_child_tot) {
+			return ebone_iter;
+		}
+	}
+
+#undef EBONE_TEMP_UINT
+
+	return NULL;
+}
+
 void ED_armature_ebone_to_mat3(EditBone *ebone, float mat[3][3])
 {
 	float delta[3];
diff --git a/source/blender/editors/include/ED_armature.h b/source/blender/editors/include/ED_armature.h
index 455378fc2ce..e9caf89d9da 100644
--- a/source/blender/editors/include/ED_armature.h
+++ b/source/blender/editors/include/ED_armature.h
@@ -138,6 +138,7 @@ struct EditBone *ED_armature_edit_bone_add(struct bArmature *arm, const char *na
 void ED_armature_edit_bone_remove(struct bArmature *arm, EditBone *exBone);
 
 bool ED_armature_ebone_is_child_recursive(EditBone *ebone_parent, EditBone *ebone_child);
+EditBone *ED_armature_bone_find_shared_parent(EditBone *ebone_child[], const unsigned int ebone_child_tot);
 
 void ED_armature_ebone_to_mat3(EditBone *ebone, float mat[3][3]);
 void ED_armature_ebone_to_mat4(EditBone *ebone, float mat[4][4]);