New hair editing feature "Shape Cut", for cutting hair based on a mesh

shape instead of a brush tool.

The brush cutting tool for hair, while useful, is not very accurate and
often requires rotating the model constantly to get the right trimming
on every side. This makes adjustments to a hair shape a very tedious
process.

On the other hand, making proxy meshes for hair shapes is a common
workflow. The new operator allows using such rough meshes as boundaries
for hair. All hairs that are outside the shape mesh are removed, while
those cutting it at some length are shortened accordingly.

The operator can be accessed in the particle edit mode toolbar via the
"Shape Cut" button. The "Shape Object" must be set first and stays
selected as a tool setting for repeatedly applying the shape.

9 files changed, 286 insertions, 1 deletions

diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c
index ccbce205b01..bf0aa4536dc 100644
--- a/source/blender/blenkernel/intern/object.c
+++ b/source/blender/blenkernel/intern/object.c
@@ -683,6 +683,7 @@ void BKE_object_unlink(Object *ob)
 			if (sce->camera == ob) sce->camera = NULL;
 			if (sce->toolsettings->skgen_template == ob) sce->toolsettings->skgen_template = NULL;
 			if (sce->toolsettings->particle.object == ob) sce->toolsettings->particle.object = NULL;
+			if (sce->toolsettings->particle.shape_object == ob) sce->toolsettings->particle.shape_object = NULL;
 
 #ifdef DURIAN_CAMERA_SWITCH
 			{
diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index 49d072ddfdc..4981b163cdf 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -105,6 +105,10 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *n
 int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit,
                          BVHTree_RayCastCallback callback, void *userdata);
 
+/* Calls the callback for every ray intersection */
+int BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3], float radius,
+                             BVHTree_RayCastCallback callback, void *userdata);
+
 float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3]);
 
 /* range query */
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index b76b925e6cc..e4504bcaab1 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -1468,6 +1468,42 @@ static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
 	}
 }
 
+static void dfs_raycast_all(BVHRayCastData *data, BVHNode *node)
+{
+	int i;
+
+	/* ray-bv is really fast.. and simple tests revealed its worth to test it
+	 * before calling the ray-primitive functions */
+	/* XXX: temporary solution for particles until fast_ray_nearest_hit supports ray.radius */
+	float dist = (data->ray.radius == 0.0f) ? fast_ray_nearest_hit(data, node) : ray_nearest_hit(data, node->bv);
+
+	if (node->totnode == 0) {
+		if (data->callback) {
+			data->hit.index = -1;
+			data->hit.dist = FLT_MAX;
+			data->callback(data->userdata, node->index, &data->ray, &data->hit);
+		}
+		else {
+			data->hit.index = node->index;
+			data->hit.dist  = dist;
+			madd_v3_v3v3fl(data->hit.co, data->ray.origin, data->ray.direction, dist);
+		}
+	}
+	else {
+		/* pick loop direction to dive into the tree (based on ray direction and split axis) */
+		if (data->ray_dot_axis[node->main_axis] > 0.0f) {
+			for (i = 0; i != node->totnode; i++) {
+				dfs_raycast_all(data, node->children[i]);
+			}
+		}
+		else {
+			for (i = node->totnode - 1; i >= 0; i--) {
+				dfs_raycast_all(data, node->children[i]);
+			}
+		}
+	}
+}
+
 #if 0
 static void iterative_raycast(BVHRayCastData *data, BVHNode *node)
 {
@@ -1573,6 +1609,48 @@ float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], cons
 	
 }
 
+int BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3], float radius,
+                             BVHTree_RayCastCallback callback, void *userdata)
+{
+	int i;
+	BVHRayCastData data;
+	BVHNode *root = tree->nodes[tree->totleaf];
+
+	data.tree = tree;
+
+	data.callback = callback;
+	data.userdata = userdata;
+
+	copy_v3_v3(data.ray.origin,    co);
+	copy_v3_v3(data.ray.direction, dir);
+	data.ray.radius = radius;
+
+	normalize_v3(data.ray.direction);
+
+	for (i = 0; i < 3; i++) {
+		data.ray_dot_axis[i] = dot_v3v3(data.ray.direction, KDOP_AXES[i]);
+		data.idot_axis[i] = 1.0f / data.ray_dot_axis[i];
+
+		if (fabsf(data.ray_dot_axis[i]) < FLT_EPSILON) {
+			data.ray_dot_axis[i] = 0.0;
+		}
+		data.index[2 * i] = data.idot_axis[i] < 0.0f ? 1 : 0;
+		data.index[2 * i + 1] = 1 - data.index[2 * i];
+		data.index[2 * i]   += 2 * i;
+		data.index[2 * i + 1] += 2 * i;
+	}
+
+
+	data.hit.index = -1;
+	data.hit.dist = FLT_MAX;
+
+	if (root) {
+		dfs_raycast_all(&data, root);
+	}
+
+	return data.hit.index;
+}
+
 /**
  * Range Query - as request by broken :P
  *
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index ebc103841cf..80dc6db8f98 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -5260,6 +5260,8 @@ static void lib_link_scene(FileData *fd, Main *main)
 			
 			sce->toolsettings->skgen_template = newlibadr(fd, sce->id.lib, sce->toolsettings->skgen_template);
 			
+			sce->toolsettings->particle.shape_object = newlibadr(fd, sce->id.lib, sce->toolsettings->particle.shape_object);
+			
 			for (base = sce->base.first; base; base = next) {
 				next = base->next;
 				
diff --git a/source/blender/editors/physics/particle_edit.c b/source/blender/editors/physics/particle_edit.c
index 9a3433b0ccf..cbed5a3b2ee 100644
--- a/source/blender/editors/physics/particle_edit.c
+++ b/source/blender/editors/physics/particle_edit.c
@@ -61,7 +61,7 @@
 #include "BKE_modifier.h"
 #include "BKE_particle.h"
 #include "BKE_report.h"
-
+#include "BKE_bvhutils.h"
 #include "BKE_pointcache.h"
 
 #include "BIF_gl.h"
@@ -355,6 +355,7 @@ typedef struct PEData {
 	Object *ob;
 	DerivedMesh *dm;
 	PTCacheEdit *edit;
+	BVHTreeFromMesh shape_bvh;
 
 	const int *mval;
 	rcti *rect;
@@ -411,6 +412,24 @@ static void PE_set_view3d_data(bContext *C, PEData *data)
 	}
 }
 
+static void PE_create_shape_tree(PEData *data, Object *shapeob)
+{
+	DerivedMesh *dm = shapeob->derivedFinal;
+	
+	memset(&data->shape_bvh, 0, sizeof(data->shape_bvh));
+	
+	if (!shapeob || !shapeob->derivedFinal)
+		return;
+	
+	DM_ensure_tessface(dm);
+	bvhtree_from_mesh_faces(&data->shape_bvh, dm, 0.0f, 4, 8);
+}
+
+static void PE_free_shape_tree(PEData *data)
+{
+	free_bvhtree_from_mesh(&data->shape_bvh);
+}
+
 /*************************** selection utilities *******************************/
 
 static bool key_test_depth(PEData *data, const float co[3], const int screen_co[2])
@@ -4032,6 +4051,178 @@ void PARTICLE_OT_brush_edit(wmOperatorType *ot)
 	RNA_def_collection_runtime(ot->srna, "stroke", &RNA_OperatorStrokeElement, "Stroke", "");
 }
 
+/*********************** cut shape ***************************/
+
+static int shape_cut_poll(bContext *C)
+{
+	if (PE_hair_poll(C)) {
+		Scene *scene= CTX_data_scene(C);
+		ParticleEditSettings *pset= PE_settings(scene);
+		
+		if (pset->shape_object)
+			return true;
+	}
+	
+	return false;
+}
+
+typedef struct PointInsideBVH {
+	BVHTreeFromMesh bvhdata;
+	int num_hits;
+} PointInsideBVH;
+
+static void point_inside_bvh_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+{
+	PointInsideBVH *data = userdata;
+	
+	data->bvhdata.raycast_callback(&data->bvhdata, index, ray, hit);
+	
+	if (hit->index != -1)
+		++data->num_hits;
+}
+
+/* true if the point is inside the shape mesh */
+static bool shape_cut_test_point(PEData *data, ParticleCacheKey *key)
+{
+	BVHTreeFromMesh *shape_bvh = &data->shape_bvh;
+	const float dir[3] = {1.0f, 0.0f, 0.0f};
+	PointInsideBVH userdata = { data->shape_bvh, 0 };
+	
+	BLI_bvhtree_ray_cast_all(shape_bvh->tree, key->co, dir, 0.0f, point_inside_bvh_cb, &userdata);
+	
+	/* for any point inside a watertight mesh the number of hits is uneven */
+	return (userdata.num_hits % 2) == 1;
+}
+
+static void shape_cut(PEData *data, int pa_index)
+{
+	PTCacheEdit *edit = data->edit;
+	Object *ob = data->ob;
+	ParticleEditSettings *pset = PE_settings(data->scene);
+	ParticleCacheKey *key;
+	
+	bool cut;
+	float cut_time = 1.0;
+	int k, totkeys = 1 << pset->draw_step;
+	
+	/* don't cut hidden */
+	if (edit->points[pa_index].flag & PEP_HIDE)
+		return;
+	
+	cut = false;
+	
+	/* check if root is inside the cut shape */
+	key = edit->pathcache[pa_index];
+	if (!shape_cut_test_point(data, key)) {
+		cut_time = -1.0f;
+		cut = true;
+	}
+	else {
+		for (k = 0; k < totkeys; k++, key++) {
+			BVHTreeRayHit hit;
+			float dir[3];
+			float len;
+			
+			sub_v3_v3v3(dir, (key+1)->co, key->co);
+			len = normalize_v3(dir);
+			
+			memset(&hit, 0, sizeof(hit));
+			hit.index = -1;
+			hit.dist = len;
+			BLI_bvhtree_ray_cast(data->shape_bvh.tree, key->co, dir, 0.0f, &hit, data->shape_bvh.raycast_callback, &data->shape_bvh);
+			if (hit.index >= 0) {
+				if (hit.dist < len) {
+//					cut_time = interpf((key+1)->time, key->time, hit.dist / len);
+					cut_time = (hit.dist / len + (float)k) / (float)totkeys;
+					cut = true;
+					break;
+				}
+			}
+		}
+	}
+
+	if (cut) {
+		if (cut_time < 0.0f) {
+			edit->points[pa_index].flag |= PEP_TAG;
+		}
+		else {
+			rekey_particle_to_time(data->scene, ob, pa_index, cut_time);
+			edit->points[pa_index].flag |= PEP_EDIT_RECALC;
+		}
+	}
+}
+
+static int shape_cut_exec(bContext *C, wmOperator *op)
+{
+	Scene *scene = CTX_data_scene(C);
+	Object *ob = CTX_data_active_object(C);
+	ParticleEditSettings *pset = PE_settings(scene);
+	PTCacheEdit *edit = PE_get_current(scene, ob);
+	Object *shapeob = pset->shape_object;
+	int selected = count_selected_keys(scene, edit);
+	int lock_root = pset->flag & PE_LOCK_FIRST;
+	
+	if (!PE_start_edit(edit))
+		return OPERATOR_CANCELLED;
+	
+	/* disable locking temporatily for disconnected hair */
+	if (edit->psys && edit->psys->flag & PSYS_GLOBAL_HAIR)
+		pset->flag &= ~PE_LOCK_FIRST;
+	
+	if (edit->psys && edit->pathcache) {
+		PEData data;
+		int removed;
+		
+		PE_set_data(C, &data);
+		PE_create_shape_tree(&data, shapeob);
+		
+		if (selected)
+			foreach_selected_point(&data, shape_cut);
+		else
+			foreach_point(&data, shape_cut);
+		
+		removed = remove_tagged_particles(ob, edit->psys, pe_x_mirror(ob));
+		recalc_lengths(edit);
+		
+		if (removed) {
+			update_world_cos(ob, edit);
+			psys_free_path_cache(NULL, edit);
+			DAG_id_tag_update(&ob->id, OB_RECALC_DATA);
+		}
+		else
+			PE_update_object(scene, ob, 1);
+		
+		if (edit->psys) {
+			WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE|NA_EDITED, ob);
+		}
+		else {
+			DAG_id_tag_update(&ob->id, OB_RECALC_DATA);
+			WM_event_add_notifier(C, NC_OBJECT|ND_MODIFIER, ob);
+		}
+		
+		PE_free_shape_tree(&data);
+	}
+	
+	pset->flag |= lock_root;
+	
+	return OPERATOR_FINISHED;
+}
+
+void PARTICLE_OT_shape_cut(wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name = "Shape Cut";
+	ot->idname = "PARTICLE_OT_shape_cut";
+	ot->description = "Cut hair to conform to the set shape object";
+	
+	/* api callbacks */
+	ot->exec = shape_cut_exec;
+	ot->poll = shape_cut_poll;
+
+	/* flags */
+	ot->flag = OPTYPE_REGISTER|OPTYPE_UNDO;
+}
+
 /*********************** undo ***************************/
 
 static void free_PTCacheUndo(PTCacheUndo *undo)
diff --git a/source/blender/editors/physics/physics_intern.h b/source/blender/editors/physics/physics_intern.h
index b8955c8c397..705235a376e 100644
--- a/source/blender/editors/physics/physics_intern.h
+++ b/source/blender/editors/physics/physics_intern.h
@@ -56,6 +56,8 @@ void PARTICLE_OT_mirror(struct wmOperatorType *ot);
 
 void PARTICLE_OT_brush_edit(struct wmOperatorType *ot);
 
+void PARTICLE_OT_shape_cut(struct wmOperatorType *ot);
+
 void PARTICLE_OT_particle_edit_toggle(struct wmOperatorType *ot);
 void PARTICLE_OT_edited_clear(struct wmOperatorType *ot);
 
diff --git a/source/blender/editors/physics/physics_ops.c b/source/blender/editors/physics/physics_ops.c
index 03d32bc052d..7f516ea2b2f 100644
--- a/source/blender/editors/physics/physics_ops.c
+++ b/source/blender/editors/physics/physics_ops.c
@@ -64,6 +64,8 @@ static void operatortypes_particle(void)
 
 	WM_operatortype_append(PARTICLE_OT_brush_edit);
 
+	WM_operatortype_append(PARTICLE_OT_shape_cut);
+
 	WM_operatortype_append(PARTICLE_OT_particle_edit_toggle);
 	WM_operatortype_append(PARTICLE_OT_edited_clear);
 
diff --git a/source/blender/makesdna/DNA_scene_types.h b/source/blender/makesdna/DNA_scene_types.h
index 9371170a004..8acfd233130 100644
--- a/source/blender/makesdna/DNA_scene_types.h
+++ b/source/blender/makesdna/DNA_scene_types.h
@@ -882,6 +882,7 @@ typedef struct ParticleEditSettings {
 
 	struct Scene *scene;
 	struct Object *object;
+	struct Object *shape_object;
 } ParticleEditSettings;
 
 /* ------------------------------------------- */
diff --git a/source/blender/makesrna/intern/rna_sculpt_paint.c b/source/blender/makesrna/intern/rna_sculpt_paint.c
index 8e83543812d..3b19e450f3b 100644
--- a/source/blender/makesrna/intern/rna_sculpt_paint.c
+++ b/source/blender/makesrna/intern/rna_sculpt_paint.c
@@ -888,6 +888,10 @@ static void rna_def_particle_edit(BlenderRNA *brna)
 	RNA_def_property_clear_flag(prop, PROP_EDITABLE);
 	RNA_def_property_ui_text(prop, "Object", "The edited object");
 
+	prop = RNA_def_property(srna, "shape_object", PROP_POINTER, PROP_NONE);
+	RNA_def_property_flag(prop, PROP_EDITABLE);
+	RNA_def_property_ui_text(prop, "Shape Object", "Outer shape to use for tools");
+	RNA_def_property_update(prop, NC_OBJECT | ND_DRAW, "rna_ParticleEdit_redo");
 
 	/* brush */