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.

release/scripts/startup/bl_ui/space_view3d_toolbar.py

@@ -1802,6 +1802,9 @@ class VIEW3D_PT_tools_particlemode(View3DPanel, Panel):
             col.prop(pe, "use_auto_velocity", text="Velocity")
         col.prop(ob.data, "use_mirror_x")
 
+        col.prop(pe, "shape_object")
+        col.operator("particle.shape_cut")
+
         col = layout.column(align=True)
         col.active = pe.is_editable
         col.label(text="Draw:")

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
 			{

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 */

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
  *

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;
 				

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)

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);
 

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);
 

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;
 
 /* ------------------------------------------- */

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 */