support for vertex parenting in object mode for object types which support it (mesh, lattice, curve, surface)

previously this had to be done one by one.

both single and triagle vertex parents can be made, selected based on distance to the verts.

Developer notes:
- looks like this was old TODO, enums existed but weren't used.
- only meshes currently support using.
- added BKE_object_as_kdtree(), may come in handy for similar cases.

5 files changed, 214 insertions, 12 deletions

diff --git a/source/blender/blenkernel/BKE_object.h b/source/blender/blenkernel/BKE_object.h
index dbd2263cfc9..8007aba2a53 100644
--- a/source/blender/blenkernel/BKE_object.h
+++ b/source/blender/blenkernel/BKE_object.h
@@ -194,6 +194,8 @@ struct LinkNode *BKE_object_relational_superset(struct Scene *scene, eObjectSet
 struct LinkNode *BKE_object_groups(struct Object *ob);
 void             BKE_object_groups_clear(struct Scene *scene, struct Base *base, struct Object *object);
 
+struct KDTree *BKE_object_as_kdtree(struct Object *ob, int *r_tot);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c
index d54ccb17710..832d2791a7d 100644
--- a/source/blender/blenkernel/intern/object.c
+++ b/source/blender/blenkernel/intern/object.c
@@ -64,6 +64,7 @@
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
 #include "BLI_linklist.h"
+#include "BLI_kdtree.h"
 
 #include "BLF_translation.h"
 
@@ -3440,3 +3441,128 @@ void BKE_object_groups_clear(Scene *scene, Base *base, Object *object)
 		BKE_group_object_unlink(group, object, scene, base);
 	}
 }
+
+/**
+ * Return a KDTree from the deformed object (in worldspace)
+ *
+ * \note Only mesh objects currently support deforming, others are TODO.
+ *
+ * \param ob
+ * \param r_tot
+ * \return The kdtree or NULL if it can't be created.
+ */
+KDTree *BKE_object_as_kdtree(Object *ob, int *r_tot)
+{
+	KDTree *tree = NULL;
+	unsigned int tot = 0;
+	float co[3];
+
+	switch (ob->type) {
+		case OB_MESH:
+		{
+			Mesh *me = ob->data;
+			unsigned int i;
+
+			DerivedMesh *dm = ob->derivedDeform ? ob->derivedDeform : ob->derivedFinal;
+			int *index;
+
+			if (dm && (index = CustomData_get_layer(&dm->vertData, CD_ORIGINDEX))) {
+				MVert *mvert = dm->getVertArray(dm);
+				unsigned int totvert = dm->getNumVerts(dm);
+
+				/* tree over-allocs in case where some verts have ORIGINDEX_NONE */
+				tot = 0;
+				tree = BLI_kdtree_new(totvert);
+
+				/* we don't how how many verts from the DM we can use */
+				for (i = 0; i < totvert; i++) {
+					if (index[i] != ORIGINDEX_NONE) {
+						mul_v3_m4v3(co, ob->obmat, mvert[i].co);
+						BLI_kdtree_insert(tree, index[i], co, NULL);
+						tot++;
+					}
+				}
+			}
+			else {
+				MVert *mvert = me->mvert;
+
+				tot = me->totvert;
+				tree = BLI_kdtree_new(tot);
+
+				for (i = 0; i < tot; i++) {
+					mul_v3_m4v3(co, ob->obmat, mvert[i].co);
+					BLI_kdtree_insert(tree, i, co, NULL);
+				}
+			}
+
+			BLI_kdtree_balance(tree);
+			break;
+		}
+		case OB_CURVE:
+		case OB_SURF:
+		{
+			/* TODO: take deformation into account */
+			Curve *cu = ob->data;
+			unsigned int i, a;
+
+			Nurb *nu;
+
+			tot = BKE_nurbList_verts_count_without_handles(&cu->nurb);
+			tree = BLI_kdtree_new(tot);
+			i = 0;
+
+			nu = cu->nurb.first;
+			while (nu) {
+				if (nu->bezt) {
+					BezTriple *bezt;
+
+					bezt = nu->bezt;
+					a = nu->pntsu;
+					while (a--) {
+						mul_v3_m4v3(co, ob->obmat, bezt->vec[1]);
+						BLI_kdtree_insert(tree, i++, co, NULL);
+						bezt++;
+					}
+				}
+				else {
+					BPoint *bp;
+
+					bp = nu->bp;
+					a = nu->pntsu * nu->pntsv;
+					while (a--) {
+						mul_v3_m4v3(co, ob->obmat, bp->vec);
+						BLI_kdtree_insert(tree, i++, co, NULL);
+						bp++;
+					}
+				}
+				nu = nu->next;
+			}
+
+			BLI_kdtree_balance(tree);
+			break;
+		}
+		case OB_LATTICE:
+		{
+			/* TODO: take deformation into account */
+			Lattice *lt = ob->data;
+			BPoint *bp;
+			unsigned int i;
+
+			tot = lt->pntsu * lt->pntsv * lt->pntsw;
+			tree = BLI_kdtree_new(tot);
+			i = 0;
+
+			for (bp = lt->def; i < tot; bp++) {
+				float co[3];
+				mul_v3_m4v3(co, ob->obmat, bp->vec);
+				BLI_kdtree_insert(tree, i++, co, NULL);
+			}
+
+			BLI_kdtree_balance(tree);
+			break;
+		}
+	}
+
+	*r_tot = tot;
+	return tree;
+}
diff --git a/source/blender/editors/include/ED_object.h b/source/blender/editors/include/ED_object.h
index bcc09cced3b..7553cb3699c 100644
--- a/source/blender/editors/include/ED_object.h
+++ b/source/blender/editors/include/ED_object.h
@@ -92,7 +92,7 @@ typedef enum eParentType {
 	PAR_PATH_CONST,
 	PAR_LATTICE,
 	PAR_VERTEX,
-	PAR_TRIA
+	PAR_VERTEX_TRI
 } eParentType;
 
 #ifdef __RNA_TYPES_H__
@@ -101,7 +101,7 @@ extern struct EnumPropertyItem prop_make_parent_types[];
 #endif
 
 int ED_object_parent_set(struct ReportList *reports, struct Main *bmain, struct Scene *scene, struct Object *ob,
-                         struct Object *par, int partype, int xmirror, int keep_transform);
+                         struct Object *par, int partype, bool xmirror, bool keep_transform, const int vert_par[3]);
 void ED_object_parent_clear(struct Object *ob, int type);
 struct Base *ED_object_scene_link(struct Scene *scene, struct Object *ob);
 
diff --git a/source/blender/editors/object/object_relations.c b/source/blender/editors/object/object_relations.c
index 52f51cfcf48..ad486d43da7 100644
--- a/source/blender/editors/object/object_relations.c
+++ b/source/blender/editors/object/object_relations.c
@@ -55,6 +55,7 @@
 #include "BLI_listbase.h"
 #include "BLI_linklist.h"
 #include "BLI_string.h"
+#include "BLI_kdtree.h"
 #include "BLI_utildefines.h"
 
 #include "BLF_translation.h"
@@ -584,12 +585,12 @@ EnumPropertyItem prop_make_parent_types[] = {
 	{PAR_PATH_CONST, "PATH_CONST", 0, "Path Constraint", ""},
 	{PAR_LATTICE, "LATTICE", 0, "Lattice Deform", ""},
 	{PAR_VERTEX, "VERTEX", 0, "Vertex", ""},
-	{PAR_TRIA, "TRIA", 0, "Triangle", ""},
+	{PAR_VERTEX_TRI, "VERTEX_TRI", 0, "Vertex (Triangle)", ""},
 	{0, NULL, 0, NULL, NULL}
 };
 
 int ED_object_parent_set(ReportList *reports, Main *bmain, Scene *scene, Object *ob, Object *par,
-                         int partype, int xmirror, int keep_transform)
+                         int partype, bool xmirror, bool keep_transform, const int vert_par[3])
 {
 	bPoseChannel *pchan = NULL;
 	int pararm = ELEM4(partype, PAR_ARMATURE, PAR_ARMATURE_NAME, PAR_ARMATURE_ENVELOPE, PAR_ARMATURE_AUTO);
@@ -718,8 +719,17 @@ int ED_object_parent_set(ReportList *reports, Main *bmain, Scene *scene, Object
 				if (pchan->bone)
 					pchan->bone->flag |= BONE_RELATIVE_PARENTING;
 			}
-			else
+			else if (partype == PAR_VERTEX) {
+				ob->partype = PARVERT1;
+				ob->par1 = vert_par[0];
+			}
+			else if (partype == PAR_VERTEX_TRI) {
+				ob->partype = PARVERT3;
+				copy_v3_v3_int(&ob->par1, vert_par);
+			}
+			else {
 				ob->partype = PAROBJECT;  /* note, dna define, not operator property */
+			}
 			
 			/* constraint */
 			if (partype == PAR_PATH_CONST) {
@@ -766,25 +776,83 @@ int ED_object_parent_set(ReportList *reports, Main *bmain, Scene *scene, Object
 	return 1;
 }
 
+
+
+static void parent_set_vert_find(KDTree *tree, Object *child, int vert_par[3], bool is_tri)
+{
+	const float *co_find = child->obmat[3];
+	if (is_tri) {
+		KDTreeNearest nearest[3];
+		int tot;
+
+		tot = BLI_kdtree_find_nearest_n(tree, co_find, NULL, nearest, 3);
+		BLI_assert(tot == 3);
+
+		vert_par[0] = nearest[0].index;
+		vert_par[1] = nearest[1].index;
+		vert_par[2] = nearest[2].index;
+
+		BLI_assert(min_iii(UNPACK3(vert_par)) >= 0);
+	}
+	else {
+		vert_par[0] = BLI_kdtree_find_nearest(tree, co_find, NULL, NULL);
+		BLI_assert(vert_par[0] >= 0);
+		vert_par[1] = 0;
+		vert_par[2] = 0;
+	}
+}
+
 static int parent_set_exec(bContext *C, wmOperator *op)
 {
 	Main *bmain = CTX_data_main(C);
 	Scene *scene = CTX_data_scene(C);
 	Object *par = ED_object_active_context(C);
 	int partype = RNA_enum_get(op->ptr, "type");
-	int xmirror = RNA_boolean_get(op->ptr, "xmirror");
-	int keep_transform = RNA_boolean_get(op->ptr, "keep_transform");
-	int ok = 1;
+	bool xmirror = RNA_boolean_get(op->ptr, "xmirror");
+	bool keep_transform = RNA_boolean_get(op->ptr, "keep_transform");
+	bool ok = true;
+
+	/* vertex parent (kdtree) */
+	const bool is_vert_par = ELEM(partype, PAR_VERTEX, PAR_VERTEX_TRI);
+	const bool is_tri = partype == PAR_VERTEX_TRI;
+	int tree_tot;
+	struct KDTree *tree = NULL;
+	int vert_par[3] = {0, 0, 0};
+	int *vert_par_p = is_vert_par ? vert_par : NULL;
+
+
+	if (is_vert_par) {
+		tree = BKE_object_as_kdtree(par, &tree_tot);
+		BLI_assert(tree != NULL);
+
+		if (tree_tot < (is_tri ? 3 : 1)) {
+			BKE_report(op->reports, RPT_ERROR, "Not enough vertices for vertex-parent");
+			ok = false;
+			goto cleanup;
+		}
+	}
+
 
+	/* Non vertex-parent */
 	CTX_DATA_BEGIN (C, Object *, ob, selected_editable_objects)
 	{
-		if (!ED_object_parent_set(op->reports, bmain, scene, ob, par, partype, xmirror, keep_transform)) {
-			ok = 0;
+		if (is_vert_par) {
+			parent_set_vert_find(tree, ob, vert_par, is_tri);
+		}
+
+		if (!ED_object_parent_set(op->reports, bmain, scene, ob, par, partype, xmirror, keep_transform, vert_par_p)) {
+			ok = false;
 			break;
 		}
 	}
 	CTX_DATA_END;
 
+
+cleanup:
+	if (is_vert_par) {
+		BLI_kdtree_free(tree);
+	}
+
 	if (!ok)
 		return OPERATOR_CANCELLED;
 
@@ -835,6 +903,12 @@ static int parent_set_invoke(bContext *C, wmOperator *UNUSED(op), const wmEvent
 		uiItemEnumO_ptr(layout, ot, NULL, 0, "type", PAR_LATTICE);
 	}
 	
+	/* vertex parenting */
+	if (ELEM4(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_LATTICE)) {
+		uiItemEnumO_ptr(layout, ot, NULL, 0, "type", PAR_VERTEX);
+		uiItemEnumO_ptr(layout, ot, NULL, 0, "type", PAR_VERTEX_TRI);
+	}
+
 	uiPupMenuEnd(C, pup);
 	
 	return OPERATOR_CANCELLED;
diff --git a/source/blender/editors/space_outliner/outliner_edit.c b/source/blender/editors/space_outliner/outliner_edit.c
index 1e9b681197c..2de8f52d677 100644
--- a/source/blender/editors/space_outliner/outliner_edit.c
+++ b/source/blender/editors/space_outliner/outliner_edit.c
@@ -1469,7 +1469,7 @@ static int parent_drop_exec(bContext *C, wmOperator *op)
 	RNA_string_get(op->ptr, "child", childname);
 	ob = (Object *)BKE_libblock_find_name(ID_OB, childname);
 
-	ED_object_parent_set(op->reports, bmain, scene, ob, par, partype, FALSE, FALSE);
+	ED_object_parent_set(op->reports, bmain, scene, ob, par, partype, false, false, NULL);
 
 	DAG_relations_tag_update(bmain);
 	WM_event_add_notifier(C, NC_OBJECT | ND_TRANSFORM, NULL);
@@ -1525,7 +1525,7 @@ static int parent_drop_invoke(bContext *C, wmOperator *op, const wmEvent *event)
 		}
 
 		if ((par->type != OB_ARMATURE) && (par->type != OB_CURVE) && (par->type != OB_LATTICE)) {
-			if (ED_object_parent_set(op->reports, bmain, scene, ob, par, partype, FALSE, FALSE)) {
+			if (ED_object_parent_set(op->reports, bmain, scene, ob, par, partype, false, false, NULL)) {
 				DAG_relations_tag_update(bmain);
 				WM_event_add_notifier(C, NC_OBJECT | ND_TRANSFORM, NULL);
 				WM_event_add_notifier(C, NC_OBJECT | ND_PARENT, NULL);