Hair editing: Multi-thread various parts

Currently focused on making parts which are a bottleneck for Spring,
to make things fast as possible. There are surely lots of places
where threading is not currently done, but we can keep doing this,
maybe even with help from the community :)

2 files changed, 617 insertions, 355 deletions

diff --git a/source/blender/blenkernel/intern/particle.c b/source/blender/blenkernel/intern/particle.c
index 127ef840027..0ae6d2a3f2d 100644
--- a/source/blender/blenkernel/intern/particle.c
+++ b/source/blender/blenkernel/intern/particle.c
@@ -2598,204 +2598,236 @@ void psys_cache_paths(ParticleSimulationData *sim, float cfra, const bool use_re
 	if (vg_length)
 		MEM_freeN(vg_length);
 }
-void psys_cache_edit_paths(Depsgraph *depsgraph, Scene *scene, Object *ob, PTCacheEdit *edit, float cfra, const bool use_render_params)
-{
-	ParticleCacheKey *ca, **cache = edit->pathcache;
-	ParticleEditSettings *pset = &scene->toolsettings->particle;
-	
-	PTCacheEditPoint *point = NULL;
-	PTCacheEditKey *ekey = NULL;
-
-	ParticleSystem *psys = edit->psys;
-	ParticleSystemModifierData *psmd = psys_get_modifier(ob, psys);
-
-	ParticleData *pa = psys ? psys->particles : NULL;
 
-	ParticleInterpolationData pind;
-	ParticleKey result;
-	
-	float birthtime = 0.0f, dietime = 0.0f;
-	float t, time = 0.0f, keytime = 0.0f /*, frs_sec */;
-	float hairmat[4][4], rotmat[3][3], prev_tangent[3] = {0.0f, 0.0f, 0.0f};
-	int k, i;
-	int segments = 1 << pset->draw_step;
-	int totpart = edit->totpoint, recalc_set = 0;
+typedef struct CacheEditrPathsIterData {
+	Object *object;
+	PTCacheEdit *edit;
+	ParticleSystemModifierData *psmd;
+	ParticleData *pa;
+	int segments;
+	bool use_weight;
 	float sel_col[3];
 	float nosel_col[3];
+} CacheEditrPathsIterData;
 
-	segments = MAX2(segments, 4);
-
-	if (!cache || edit->totpoint != edit->totcached) {
-		/* clear out old and create new empty path cache */
-		psys_free_path_cache(edit->psys, edit);
-		cache = edit->pathcache = psys_alloc_path_cache_buffers(&edit->pathcachebufs, totpart, segments + 1);
-
-		/* set flag for update (child particles check this too) */
-		for (i = 0, point = edit->points; i < totpart; i++, point++)
-			point->flag |= PEP_EDIT_RECALC;
-		recalc_set = 1;
+static void psys_cache_edit_paths_iter(
+        void *__restrict iter_data_v,
+        const int iter,
+        const ParallelRangeTLS *__restrict UNUSED(tls))
+{
+	CacheEditrPathsIterData *iter_data = (CacheEditrPathsIterData *)iter_data_v;
+	PTCacheEdit *edit = iter_data->edit;
+	PTCacheEditPoint *point = &edit->points[iter];
+	if (edit->totcached && !(point->flag & PEP_EDIT_RECALC)) {
+		return;
+	}
+	if (point->totkey == 0) {
+		return;
 	}
+	Object *ob = iter_data->object;
+	ParticleSystem *psys = edit->psys;
+	ParticleCacheKey **cache = edit->pathcache;
+	ParticleSystemModifierData *psmd = iter_data->psmd;
+	ParticleData *pa = iter_data->pa ? iter_data->pa + iter : NULL;
+	PTCacheEditKey *ekey = point->keys;
+	const int segments = iter_data->segments;
+	const bool use_weight = iter_data->use_weight;
 
-	/* frs_sec = (psys || edit->pid.flag & PTCACHE_VEL_PER_SEC) ? 25.0f : 1.0f; */ /* UNUSED */
+	float birthtime = 0.0f, dietime = 0.0f;
+	float hairmat[4][4], rotmat[3][3], prev_tangent[3] = {0.0f, 0.0f, 0.0f};
 
-	const bool use_weight = (pset->brushtype == PE_BRUSH_WEIGHT) && (psys != NULL) && (psys->particles != NULL);
+	ParticleInterpolationData pind;
+	pind.keyed = 0;
+	pind.cache = NULL;
+	pind.epoint = point;
+	pind.bspline = psys ? (psys->part->flag & PART_HAIR_BSPLINE) : 0;
+	pind.mesh = NULL;
 
+	/* should init_particle_interpolation set this ? */
 	if (use_weight) {
-		; /* use weight painting colors now... */
-	}
-	else {
-		sel_col[0] = (float)edit->sel_col[0] / 255.0f;
-		sel_col[1] = (float)edit->sel_col[1] / 255.0f;
-		sel_col[2] = (float)edit->sel_col[2] / 255.0f;
-		nosel_col[0] = (float)edit->nosel_col[0] / 255.0f;
-		nosel_col[1] = (float)edit->nosel_col[1] / 255.0f;
-		nosel_col[2] = (float)edit->nosel_col[2] / 255.0f;
+		pind.hkey[0] = NULL;
+		/* pa != NULL since the weight brush is only available for hair */
+		pind.hkey[0] = pa->hair;
+		pind.hkey[1] = pa->hair + 1;
 	}
 
-	/*---first main loop: create all actual particles' paths---*/
-	for (i = 0, point = edit->points; i < totpart; i++, pa += pa ? 1 : 0, point++) {
-		if (edit->totcached && !(point->flag & PEP_EDIT_RECALC))
-			continue;
+	memset(cache[iter], 0, sizeof(*cache[iter]) * (segments + 1));
 
-		if (point->totkey == 0)
-			continue;
+	cache[iter]->segments = segments;
 
-		ekey = point->keys;
+	/*--get the first data points--*/
+	init_particle_interpolation(ob, psys, pa, &pind);
 
-		pind.keyed = 0;
-		pind.cache = NULL;
-		pind.epoint = point;
-		pind.bspline = psys ? (psys->part->flag & PART_HAIR_BSPLINE) : 0;
-		pind.mesh = NULL;
+	if (psys) {
+		psys_mat_hair_to_global(ob, psmd->mesh_final, psys->part->from, pa, hairmat);
+		copy_v3_v3(rotmat[0], hairmat[2]);
+		copy_v3_v3(rotmat[1], hairmat[1]);
+		copy_v3_v3(rotmat[2], hairmat[0]);
+	}
 
+	birthtime = pind.birthtime;
+	dietime = pind.dietime;
 
-		/* should init_particle_interpolation set this ? */
-		if (use_weight) {
-			pind.hkey[0] = NULL;
-			/* pa != NULL since the weight brush is only available for hair */
-			pind.hkey[0] = pa->hair;
-			pind.hkey[1] = pa->hair + 1;
-		}
+	if (birthtime >= dietime) {
+		cache[iter]->segments = -1;
+		return;
+	}
 
+	/*--interpolate actual path from data points--*/
+	ParticleCacheKey *ca;
+	int k;
+	float t, time = 0.0f, keytime = 0.0f;
+	for (k = 0, ca = cache[iter]; k <= segments; k++, ca++) {
+		time = (float)k / (float)segments;
+		t = birthtime + time * (dietime - birthtime);
+		ParticleKey result;
+		result.time = -t;
+		do_particle_interpolation(psys, iter, pa, t, &pind, &result);
+		copy_v3_v3(ca->co, result.co);
+
+		/* non-hair points are already in global space */
+		if (psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
+			mul_m4_v3(hairmat, ca->co);
 
-		memset(cache[i], 0, sizeof(*cache[i]) * (segments + 1));
+			if (k) {
+				cache_key_incremental_rotation(ca, ca - 1, ca - 2, prev_tangent, k);
 
-		cache[i]->segments = segments;
+				if (k == segments)
+					copy_qt_qt(ca->rot, (ca - 1)->rot);
 
-		/*--get the first data points--*/
-		init_particle_interpolation(ob, psys, pa, &pind);
+				/* set velocity */
+				sub_v3_v3v3(ca->vel, ca->co, (ca - 1)->co);
 
-		if (psys) {
-			psys_mat_hair_to_global(ob, psmd->mesh_final, psys->part->from, pa, hairmat);
-			copy_v3_v3(rotmat[0], hairmat[2]);
-			copy_v3_v3(rotmat[1], hairmat[1]);
-			copy_v3_v3(rotmat[2], hairmat[0]);
+				if (k == 1)
+					copy_v3_v3((ca - 1)->vel, ca->vel);
+			}
 		}
-
-		birthtime = pind.birthtime;
-		dietime = pind.dietime;
-
-		if (birthtime >= dietime) {
-			cache[i]->segments = -1;
-			continue;
+		else {
+			ca->vel[0] = ca->vel[1] = 0.0f;
+			ca->vel[2] = 1.0f;
 		}
 
-		/*--interpolate actual path from data points--*/
-		for (k = 0, ca = cache[i]; k <= segments; k++, ca++) {
-			time = (float)k / (float)segments;
-			t = birthtime + time * (dietime - birthtime);
-			result.time = -t;
-			do_particle_interpolation(psys, i, pa, t, &pind, &result);
-			copy_v3_v3(ca->co, result.co);
-
-			/* non-hair points are already in global space */
-			if (psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
-				mul_m4_v3(hairmat, ca->co);
-
-				if (k) {
-					cache_key_incremental_rotation(ca, ca - 1, ca - 2, prev_tangent, k);
-
-					if (k == segments)
-						copy_qt_qt(ca->rot, (ca - 1)->rot);
-
-					/* set velocity */
-					sub_v3_v3v3(ca->vel, ca->co, (ca - 1)->co);
-
-					if (k == 1)
-						copy_v3_v3((ca - 1)->vel, ca->vel);
-				}
+		/* selection coloring in edit mode */
+		if (use_weight) {
+			if (k == 0) {
+				weight_to_rgb(ca->col, pind.hkey[1]->weight);
 			}
 			else {
-				ca->vel[0] = ca->vel[1] = 0.0f;
-				ca->vel[2] = 1.0f;
-			}
-
-			/* selection coloring in edit mode */
-			if (use_weight) {
-				if (k == 0) {
-					weight_to_rgb(ca->col, pind.hkey[1]->weight);
+				/* warning: copied from 'do_particle_interpolation' (without 'mvert' array stepping) */
+				float real_t;
+				if (result.time < 0.0f) {
+					real_t = -result.time;
 				}
 				else {
-					/* warning: copied from 'do_particle_interpolation' (without 'mvert' array stepping) */
-					float real_t;
-					if (result.time < 0.0f) {
-						real_t = -result.time;
-					}
-					else {
-						real_t = pind.hkey[0]->time + t * (pind.hkey[0][pa->totkey - 1].time - pind.hkey[0]->time);
-					}
+					real_t = pind.hkey[0]->time + t * (pind.hkey[0][pa->totkey - 1].time - pind.hkey[0]->time);
+				}
 
-					while (pind.hkey[1]->time < real_t) {
-						pind.hkey[1]++;
-					}
-					pind.hkey[0] = pind.hkey[1] - 1;
-					/* end copy */
+				while (pind.hkey[1]->time < real_t) {
+					pind.hkey[1]++;
+				}
+				pind.hkey[0] = pind.hkey[1] - 1;
+				/* end copy */
 
 
-					float w1[3], w2[3];
-					keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
+				float w1[3], w2[3];
+				keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
 
-					weight_to_rgb(w1, pind.hkey[0]->weight);
-					weight_to_rgb(w2, pind.hkey[1]->weight);
+				weight_to_rgb(w1, pind.hkey[0]->weight);
+				weight_to_rgb(w2, pind.hkey[1]->weight);
 
-					interp_v3_v3v3(ca->col, w1, w2, keytime);
+				interp_v3_v3v3(ca->col, w1, w2, keytime);
+			}
+		}
+		else {
+			if ((ekey + (pind.ekey[0] - point->keys))->flag & PEK_SELECT) {
+				if ((ekey + (pind.ekey[1] - point->keys))->flag & PEK_SELECT) {
+					copy_v3_v3(ca->col, iter_data->sel_col);
+				}
+				else {
+					keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
+					interp_v3_v3v3(ca->col, iter_data->sel_col, iter_data->nosel_col, keytime);
 				}
 			}
 			else {
-				if ((ekey + (pind.ekey[0] - point->keys))->flag & PEK_SELECT) {
-					if ((ekey + (pind.ekey[1] - point->keys))->flag & PEK_SELECT) {
-						copy_v3_v3(ca->col, sel_col);
-					}
-					else {
-						keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
-						interp_v3_v3v3(ca->col, sel_col, nosel_col, keytime);
-					}
+				if ((ekey + (pind.ekey[1] - point->keys))->flag & PEK_SELECT) {
+					keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
+					interp_v3_v3v3(ca->col, iter_data->nosel_col, iter_data->sel_col, keytime);
 				}
 				else {
-					if ((ekey + (pind.ekey[1] - point->keys))->flag & PEK_SELECT) {
-						keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
-						interp_v3_v3v3(ca->col, nosel_col, sel_col, keytime);
-					}
-					else {
-						copy_v3_v3(ca->col, nosel_col);
-					}
+					copy_v3_v3(ca->col, iter_data->nosel_col);
 				}
 			}
-
-			ca->time = t;
 		}
-		if (psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
-			/* First rotation is based on emitting face orientation.
-			 * This is way better than having flipping rotations resulting
-			 * from using a global axis as a rotation pole (vec_to_quat()).
-			 * It's not an ideal solution though since it disregards the
-			 * initial tangent, but taking that in to account will allow
-			 * the possibility of flipping again. -jahka
-			 */
-			mat3_to_quat_is_ok(cache[i]->rot, rotmat);
+
+		ca->time = t;
+	}
+	if (psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
+		/* First rotation is based on emitting face orientation.
+		 * This is way better than having flipping rotations resulting
+		 * from using a global axis as a rotation pole (vec_to_quat()).
+		 * It's not an ideal solution though since it disregards the
+		 * initial tangent, but taking that in to account will allow
+		 * the possibility of flipping again. -jahka
+		 */
+		mat3_to_quat_is_ok(cache[iter]->rot, rotmat);
+	}
+}
+
+void psys_cache_edit_paths(Depsgraph *depsgraph, Scene *scene, Object *ob, PTCacheEdit *edit, float cfra, const bool use_render_params)
+{
+	ParticleCacheKey **cache = edit->pathcache;
+	ParticleEditSettings *pset = &scene->toolsettings->particle;
+	
+	ParticleSystem *psys = edit->psys;
+	ParticleSystemModifierData *psmd = psys_get_modifier(ob, psys);
+
+	ParticleData *pa = psys ? psys->particles : NULL;
+
+	int segments = 1 << pset->draw_step;
+	int totpart = edit->totpoint, recalc_set = 0;
+
+	segments = MAX2(segments, 4);
+
+	if (!cache || edit->totpoint != edit->totcached) {
+		/* Clear out old and create new empty path cache. */
+		psys_free_path_cache(edit->psys, edit);
+		cache = edit->pathcache = psys_alloc_path_cache_buffers(&edit->pathcachebufs, totpart, segments + 1);
+		/* Set flag for update (child particles check this too). */
+		int i;
+		PTCacheEditPoint *point;
+		for (i = 0, point = edit->points; i < totpart; i++, point++) {
+			point->flag |= PEP_EDIT_RECALC;
 		}
+		recalc_set = 1;
 	}
 
+	const bool use_weight = (pset->brushtype == PE_BRUSH_WEIGHT) && (psys != NULL) && (psys->particles != NULL);
+
+	CacheEditrPathsIterData iter_data;
+	iter_data.object = ob;
+	iter_data.edit = edit;
+	iter_data.psmd = psmd;
+	iter_data.pa = pa;
+	iter_data.segments = segments;
+	iter_data.use_weight = use_weight;
+
+	if (use_weight) {
+		; /* use weight painting colors now... */
+	}
+	else {
+		iter_data.sel_col[0] = (float)edit->sel_col[0] / 255.0f;
+		iter_data.sel_col[1] = (float)edit->sel_col[1] / 255.0f;
+		iter_data.sel_col[2] = (float)edit->sel_col[2] / 255.0f;
+		iter_data.nosel_col[0] = (float)edit->nosel_col[0] / 255.0f;
+		iter_data.nosel_col[1] = (float)edit->nosel_col[1] / 255.0f;
+		iter_data.nosel_col[2] = (float)edit->nosel_col[2] / 255.0f;
+	}
+
+	ParallelRangeSettings settings;
+	BLI_parallel_range_settings_defaults(&settings);
+	settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
+	BLI_task_parallel_range(0, edit->totpoint, &iter_data, psys_cache_edit_paths_iter, &settings);
+
 	edit->totcached = totpart;
 
 	if (psys) {
@@ -2811,8 +2843,11 @@ void psys_cache_edit_paths(Depsgraph *depsgraph, Scene *scene, Object *ob, PTCac
 
 	/* clear recalc flag if set here */
 	if (recalc_set) {
-		for (i = 0, point = edit->points; i < totpart; i++, point++)
+		PTCacheEditPoint *point;
+		int i;
+		for (i = 0, point = edit->points; i < totpart; i++, point++) {
 			point->flag &= ~PEP_EDIT_RECALC;
+		}
 	}
 }
 /************************************************/
diff --git a/source/blender/editors/physics/particle_edit.c b/source/blender/editors/physics/particle_edit.c
index 78cc47cd1ba..0ba98d758c7 100644
--- a/source/blender/editors/physics/particle_edit.c
+++ b/source/blender/editors/physics/particle_edit.c
@@ -49,6 +49,7 @@
 #include "BLI_string.h"
 #include "BLI_kdtree.h"
 #include "BLI_rand.h"
+#include "BLI_task.h"
 #include "BLI_utildefines.h"
 
 #include "BKE_context.h"
@@ -92,6 +93,8 @@
 
 #include "DEG_depsgraph_query.h"
 
+#include "PIL_time_utildefines.h"
+
 #include "physics_intern.h"
 
 #include "particle_edit_utildefines.h"
@@ -645,61 +648,92 @@ static void foreach_mouse_hit_point(PEData *data, ForPointFunc func, int selecte
 	}
 }
 
-static void foreach_mouse_hit_key(PEData *data, ForKeyMatFunc func, int selected)
+typedef struct KeyIterData {
+	PEData *data;
+	PTCacheEdit *edit;
+	ParticleSystemModifierData *psmd;
+	int selected;
+	ForKeyMatFunc func;
+} KeyIterData;
+
+static void foreach_mouse_hit_key_iter(
+        void *__restrict iter_data_v,
+        const int iter,
+        const ParallelRangeTLS *__restrict UNUSED(tls))
 {
+	KeyIterData *iter_data = (KeyIterData *)iter_data_v;
+	PEData *data = iter_data->data;
 	PTCacheEdit *edit = data->edit;
+	PTCacheEditPoint *point = &edit->points[iter];
+	if (point->flag & PEP_HIDE) {
+		return;
+	}
 	ParticleSystem *psys = edit->psys;
-	ParticleSystemModifierData *psmd = NULL;
-	ParticleEditSettings *pset= PE_settings(data->scene);
-	POINT_P; KEY_K;
+	ParticleSystemModifierData *psmd = iter_data->psmd;
+	ParticleEditSettings *pset = PE_settings(data->scene);
+	const int selected = iter_data->selected;
 	float mat[4][4], imat[4][4];
-
 	unit_m4(mat);
 	unit_m4(imat);
-
-	if (edit->psys)
-		psmd= psys_get_modifier(data->ob, edit->psys);
-
-	/* all is selected in path mode */
-	if (pset->selectmode==SCE_SELECT_PATH)
-		selected= 0;
-
-	LOOP_VISIBLE_POINTS {
-		if (pset->selectmode==SCE_SELECT_END) {
-			if (point->totkey) {
-				/* only do end keys */
-				key= point->keys + point->totkey-1;
-
-				if (selected==0 || key->flag & PEK_SELECT) {
-					if (key_inside_circle(data, data->rad, KEY_WCO, &data->dist)) {
-						if (edit->psys && !(edit->psys->flag & PSYS_GLOBAL_HAIR)) {
-							psys_mat_hair_to_global(data->ob, psmd->mesh_final, psys->part->from, psys->particles + p, mat);
-							invert_m4_m4(imat, mat);
-						}
-
-						func(data, mat, imat, p, point->totkey-1, key);
+	if (pset->selectmode==SCE_SELECT_END) {
+		if (point->totkey) {
+			/* only do end keys */
+			PTCacheEditKey *key = point->keys + point->totkey-1;
+
+			if (selected==0 || key->flag & PEK_SELECT) {
+				if (key_inside_circle(data, data->rad, KEY_WCO, &data->dist)) {
+					if (edit->psys && !(edit->psys->flag & PSYS_GLOBAL_HAIR)) {
+						psys_mat_hair_to_global(data->ob, psmd->mesh_final, psys->part->from, psys->particles + iter, mat);
+						invert_m4_m4(imat, mat);
 					}
+					iter_data->func(data, mat, imat, iter, point->totkey-1, key);
 				}
 			}
 		}
-		else {
-			/* do all keys */
-			LOOP_VISIBLE_KEYS {
-				if (selected==0 || key->flag & PEK_SELECT) {
-					if (key_inside_circle(data, data->rad, KEY_WCO, &data->dist)) {
-						if (edit->psys && !(edit->psys->flag & PSYS_GLOBAL_HAIR)) {
-							psys_mat_hair_to_global(data->ob, psmd->mesh_final, psys->part->from, psys->particles + p, mat);
-							invert_m4_m4(imat, mat);
-						}
-
-						func(data, mat, imat, p, k, key);
+	}
+	else {
+		/* do all keys */
+		PTCacheEditKey *key;
+		int k;
+		LOOP_VISIBLE_KEYS {
+			if (selected==0 || key->flag & PEK_SELECT) {
+				if (key_inside_circle(data, data->rad, KEY_WCO, &data->dist)) {
+					if (edit->psys && !(edit->psys->flag & PSYS_GLOBAL_HAIR)) {
+						psys_mat_hair_to_global(data->ob, psmd->mesh_final, psys->part->from, psys->particles + iter, mat);
+						invert_m4_m4(imat, mat);
 					}
+					iter_data->func(data, mat, imat, iter, k, key);
 				}
 			}
 		}
 	}
 }
 
+static void foreach_mouse_hit_key(PEData *data, ForKeyMatFunc func, int selected)
+{
+	PTCacheEdit *edit = data->edit;
+	ParticleSystemModifierData *psmd = NULL;
+	ParticleEditSettings *pset = PE_settings(data->scene);
+	if (edit->psys != NULL) {
+		psmd= psys_get_modifier(data->ob, edit->psys);
+	}
+	/* all is selected in path mode */
+	if (pset->selectmode == SCE_SELECT_PATH) {
+		selected = 0;
+	}
+
+	KeyIterData iter_data;
+	iter_data.data = data;
+	iter_data.psmd = psmd;
+	iter_data.selected = selected;
+	iter_data.func = func;
+
+	ParallelRangeSettings settings;
+	BLI_parallel_range_settings_defaults(&settings);
+	settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
+	BLI_task_parallel_range(0, edit->totpoint, &iter_data, foreach_mouse_hit_key_iter, &settings);
+}
+
 static void foreach_selected_point(PEData *data, ForPointFunc func)
 {
 	PTCacheEdit *edit = data->edit;
@@ -942,110 +976,156 @@ static void PE_apply_mirror(Object *ob, ParticleSystem *psys)
 /************************************************/
 /*			Edit Calculation					*/
 /************************************************/
-/* tries to stop edited particles from going through the emitter's surface */
-static void pe_deflect_emitter(Scene *scene, Object *ob, PTCacheEdit *edit)
-{
-	ParticleEditSettings *pset= PE_settings(scene);
+
+typedef struct DeflectEmitterIter {
+	Object *object;
 	ParticleSystem *psys;
 	ParticleSystemModifierData *psmd;
-	POINT_P; KEY_K;
+	PTCacheEdit *edit;
+	float dist;
+	float emitterdist;
+} DeflectEmitterIter;
+
+static void deflect_emitter_iter(
+        void *__restrict iter_data_v,
+        const int iter,
+        const ParallelRangeTLS *__restrict UNUSED(tls))
+ {
+	DeflectEmitterIter *iter_data = (DeflectEmitterIter *)iter_data_v;
+	PTCacheEdit *edit = iter_data->edit;
+	PTCacheEditPoint *point = &edit->points[iter];
+	if ((point->flag & PEP_EDIT_RECALC) == 0) {
+		return;
+	}
+	Object *object = iter_data->object;
+	ParticleSystem *psys = iter_data->psys;
+	ParticleSystemModifierData *psmd = iter_data->psmd;
+	PTCacheEditKey *key;
+	int k;
+	float hairimat[4][4], hairmat[4][4];
 	int index;
 	float *vec, *nor, dvec[3], dot, dist_1st=0.0f;
-	float hairimat[4][4], hairmat[4][4];
-	const float dist = ED_view3d_select_dist_px() * 0.01f;
-
-	if (edit==NULL || edit->psys==NULL || (pset->flag & PE_DEFLECT_EMITTER)==0 || (edit->psys->flag & PSYS_GLOBAL_HAIR))
-		return;
-
-	psys = edit->psys;
-	psmd = psys_get_modifier(ob, psys);
+	const float dist = iter_data->dist;
+	const float emitterdist = iter_data->emitterdist;
+	psys_mat_hair_to_object(object,
+	                        psmd->mesh_final,
+	                        psys->part->from,
+	                        psys->particles + iter,
+	                        hairmat);
 
-	if (!psmd->mesh_final)
-		return;
-
-	LOOP_EDITED_POINTS {
-		psys_mat_hair_to_object(ob, psmd->mesh_final, psys->part->from, psys->particles + p, hairmat);
+	LOOP_KEYS {
+		mul_m4_v3(hairmat, key->co);
+	}
 
-		LOOP_KEYS {
-			mul_m4_v3(hairmat, key->co);
+	LOOP_KEYS {
+		if (k == 0) {
+			dist_1st = len_v3v3((key + 1)->co, key->co);
+			dist_1st *= dist * emitterdist;
 		}
+		else {
+			index = BLI_kdtree_find_nearest(edit->emitter_field, key->co, NULL);
 
-		LOOP_KEYS {
-			if (k==0) {
-				dist_1st = len_v3v3((key+1)->co, key->co);
-				dist_1st *= dist * pset->emitterdist;
-			}
-			else {
-				index= BLI_kdtree_find_nearest(edit->emitter_field, key->co, NULL);
-
-				vec=edit->emitter_cosnos +index*6;
-				nor=vec+3;
+			vec = edit->emitter_cosnos + index * 6;
+			nor = vec + 3;
 
-				sub_v3_v3v3(dvec, key->co, vec);
+			sub_v3_v3v3(dvec, key->co, vec);
 
-				dot=dot_v3v3(dvec, nor);
-				copy_v3_v3(dvec, nor);
+			dot = dot_v3v3(dvec, nor);
+			copy_v3_v3(dvec, nor);
 
-				if (dot>0.0f) {
-					if (dot<dist_1st) {
-						normalize_v3(dvec);
-						mul_v3_fl(dvec, dist_1st-dot);
-						add_v3_v3(key->co, dvec);
-					}
-				}
-				else {
+			if (dot > 0.0f) {
+				if (dot < dist_1st) {
 					normalize_v3(dvec);
-					mul_v3_fl(dvec, dist_1st-dot);
+					mul_v3_fl(dvec, dist_1st - dot);
 					add_v3_v3(key->co, dvec);
 				}
-				if (k==1)
-					dist_1st*=1.3333f;
+			}
+			else {
+				normalize_v3(dvec);
+				mul_v3_fl(dvec, dist_1st - dot);
+				add_v3_v3(key->co, dvec);
+			}
+			if (k == 1) {
+				dist_1st *= 1.3333f;
 			}
 		}
+	}
 
-		invert_m4_m4(hairimat, hairmat);
+	invert_m4_m4(hairimat, hairmat);
 
-		LOOP_KEYS {
-			mul_m4_v3(hairimat, key->co);
-		}
+	LOOP_KEYS {
+		mul_m4_v3(hairimat, key->co);
 	}
 }
-/* force set distances between neighboring keys */
-static void PE_apply_lengths(Scene *scene, PTCacheEdit *edit)
-{
 
-	ParticleEditSettings *pset=PE_settings(scene);
-	POINT_P; KEY_K;
-	float dv1[3];
+/* tries to stop edited particles from going through the emitter's surface */
+static void pe_deflect_emitter(Scene *scene, Object *ob, PTCacheEdit *edit)
+{
+	ParticleEditSettings *pset = PE_settings(scene);
+	ParticleSystem *psys;
+	ParticleSystemModifierData *psmd;
+	const float dist = ED_view3d_select_dist_px() * 0.01f;
 
-	if (edit==0 || (pset->flag & PE_KEEP_LENGTHS)==0)
+	if (edit == NULL || edit->psys == NULL ||
+	    (pset->flag & PE_DEFLECT_EMITTER) == 0 ||
+	    (edit->psys->flag & PSYS_GLOBAL_HAIR))
+	{
 		return;
+	}
 
-	if (edit->psys && edit->psys->flag & PSYS_GLOBAL_HAIR)
+	psys = edit->psys;
+	psmd = psys_get_modifier(ob, psys);
+
+	if (!psmd->mesh_final) {
 		return;
+	}
 
-	LOOP_EDITED_POINTS {
-		LOOP_KEYS {
-			if (k) {
-				sub_v3_v3v3(dv1, key->co, (key - 1)->co);
-				normalize_v3(dv1);
-				mul_v3_fl(dv1, (key - 1)->length);
-				add_v3_v3v3(key->co, (key - 1)->co, dv1);
-			}
+	DeflectEmitterIter iter_data;
+	iter_data.object = ob;
+	iter_data.psys = psys;
+	iter_data.psmd = psmd;
+	iter_data.edit = edit;
+	iter_data.dist = dist;
+	iter_data.emitterdist = pset->emitterdist;
+
+	ParallelRangeSettings settings;
+	BLI_parallel_range_settings_defaults(&settings);
+	settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
+	BLI_task_parallel_range(0, edit->totpoint, &iter_data, deflect_emitter_iter, &settings);
+}
+
+typedef struct ApplyLengthsIterData {
+	PTCacheEdit *edit;
+} ApplyLengthsIterData;
+
+static void apply_lengths_iter(
+        void *__restrict iter_data_v,
+        const int iter,
+        const ParallelRangeTLS *__restrict UNUSED(tls))
+ {
+	ApplyLengthsIterData *iter_data = (ApplyLengthsIterData *)iter_data_v;
+	PTCacheEdit *edit = iter_data->edit;
+	PTCacheEditPoint *point = &edit->points[iter];
+	if ((point->flag & PEP_EDIT_RECALC) == 0) {
+		return;
+	}
+	PTCacheEditKey *key;
+	int k;
+	LOOP_KEYS {
+		if (k) {
+			float dv1[3];
+			sub_v3_v3v3(dv1, key->co, (key - 1)->co);
+			normalize_v3(dv1);
+			mul_v3_fl(dv1, (key - 1)->length);
+			add_v3_v3v3(key->co, (key - 1)->co, dv1);
 		}
 	}
 }
-/* try to find a nice solution to keep distances between neighboring keys */
-static void pe_iterate_lengths(Scene *scene, PTCacheEdit *edit)
+
+/* force set distances between neighboring keys */
+static void PE_apply_lengths(Scene *scene, PTCacheEdit *edit)
 {
 	ParticleEditSettings *pset=PE_settings(scene);
-	POINT_P;
-	PTCacheEditKey *key;
-	int j, k;
-	float tlen;
-	float dv0[3] = {0.0f, 0.0f, 0.0f};
-	float dv1[3] = {0.0f, 0.0f, 0.0f};
-	float dv2[3] = {0.0f, 0.0f, 0.0f};
 
 	if (edit==0 || (pset->flag & PE_KEEP_LENGTHS)==0)
 		return;
@@ -1053,43 +1133,91 @@ static void pe_iterate_lengths(Scene *scene, PTCacheEdit *edit)
 	if (edit->psys && edit->psys->flag & PSYS_GLOBAL_HAIR)
 		return;
 
-	LOOP_EDITED_POINTS {
-		for (j=1; j<point->totkey; j++) {
-			float mul= 1.0f / (float)point->totkey;
-
-			if (pset->flag & PE_LOCK_FIRST) {
-				key= point->keys + 1;
-				k= 1;
-				dv1[0] = dv1[1] = dv1[2] = 0.0;
-			}
-			else {
-				key= point->keys;
-				k= 0;
-				dv0[0] = dv0[1] = dv0[2] = 0.0;
-			}
-
-			for (; k<point->totkey; k++, key++) {
-				if (k) {
-					sub_v3_v3v3(dv0, (key - 1)->co, key->co);
-					tlen= normalize_v3(dv0);
-					mul_v3_fl(dv0, (mul * (tlen - (key - 1)->length)));
-				}
+	ApplyLengthsIterData iter_data;
+	iter_data.edit = edit;
 
-				if (k < point->totkey - 1) {
-					sub_v3_v3v3(dv2, (key + 1)->co, key->co);
-					tlen= normalize_v3(dv2);
-					mul_v3_fl(dv2, mul * (tlen - key->length));
-				}
+	ParallelRangeSettings settings;
+	BLI_parallel_range_settings_defaults(&settings);
+	settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
+	BLI_task_parallel_range(0, edit->totpoint, &iter_data, apply_lengths_iter, &settings);
+}
 
-				if (k) {
-					add_v3_v3((key-1)->co, dv1);
-				}
+typedef struct IterateLengthsIterData {
+	PTCacheEdit *edit;
+	ParticleEditSettings *pset;
+} IterateLengthsIterData;
+
+static void iterate_lengths_iter(
+        void *__restrict iter_data_v,
+        const int iter,
+        const ParallelRangeTLS *__restrict UNUSED(tls))
+{
+	IterateLengthsIterData *iter_data = (IterateLengthsIterData *)iter_data_v;
+	PTCacheEdit *edit = iter_data->edit;
+	PTCacheEditPoint *point = &edit->points[iter];
+	if ((point->flag & PEP_EDIT_RECALC) == 0) {
+		return;
+	}
+	ParticleEditSettings *pset = iter_data->pset;
+	float tlen;
+	float dv0[3] = {0.0f, 0.0f, 0.0f};
+	float dv1[3] = {0.0f, 0.0f, 0.0f};
+	float dv2[3] = {0.0f, 0.0f, 0.0f};
+	for (int j = 1; j < point->totkey; j++) {
+		PTCacheEditKey *key;
+		int k;
+		float mul = 1.0f / (float)point->totkey;
+		if (pset->flag & PE_LOCK_FIRST) {
+			key = point->keys + 1;
+			k = 1;
+			dv1[0] = dv1[1] = dv1[2] = 0.0;
+		}
+		else {
+			key = point->keys;
+			k = 0;
+			dv0[0] = dv0[1] = dv0[2] = 0.0;
+		}
 
-				add_v3_v3v3(dv1, dv0, dv2);
+		for (; k < point->totkey; k++, key++) {
+			if (k) {
+				sub_v3_v3v3(dv0, (key - 1)->co, key->co);
+				tlen = normalize_v3(dv0);
+				mul_v3_fl(dv0, (mul * (tlen - (key - 1)->length)));
+			}
+			if (k < point->totkey - 1) {
+				sub_v3_v3v3(dv2, (key + 1)->co, key->co);
+				tlen = normalize_v3(dv2);
+				mul_v3_fl(dv2, mul * (tlen - key->length));
+			}
+			if (k) {
+				add_v3_v3((key-1)->co, dv1);
 			}
+			add_v3_v3v3(dv1, dv0, dv2);
 		}
 	}
 }
+
+/* try to find a nice solution to keep distances between neighboring keys */
+static void pe_iterate_lengths(Scene *scene, PTCacheEdit *edit)
+{
+	ParticleEditSettings *pset = PE_settings(scene);
+	if (edit==0 || (pset->flag & PE_KEEP_LENGTHS)==0) {
+		return;
+	}
+	if (edit->psys && edit->psys->flag & PSYS_GLOBAL_HAIR) {
+		return;
+	}
+
+	IterateLengthsIterData iter_data;
+	iter_data.edit = edit;
+	iter_data.pset = pset;
+
+	ParallelRangeSettings settings;
+	BLI_parallel_range_settings_defaults(&settings);
+	settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
+	BLI_task_parallel_range(0, edit->totpoint, &iter_data, iterate_lengths_iter, &settings);
+}
+
 /* set current distances to be kept between neighbouting keys */
 void recalc_lengths(PTCacheEdit *edit)
 {
@@ -3359,14 +3487,13 @@ static void intersect_dm_quad_weights(const float v1[3], const float v2[3], cons
 }
 
 /* check intersection with a derivedmesh */
-static int particle_intersect_mesh(const bContext *C, Scene *scene, Object *ob, Mesh *mesh,
-                                 float *vert_cos,
-                                 const float co1[3], const float co2[3],
-                                 float *min_d, int *min_face, float *min_w,
-                                 float *face_minmax, float *pa_minmax,
-                                 float radius, float *ipoint)
+static int particle_intersect_mesh(Depsgraph *depsgraph, Scene *scene, Object *ob, Mesh *mesh,
+                                   float *vert_cos,
+                                   const float co1[3], const float co2[3],
+                                   float *min_d, int *min_face, float *min_w,
+                                   float *face_minmax, float *pa_minmax,
+                                   float radius, float *ipoint)
 {
-	Depsgraph *depsgraph = CTX_data_depsgraph(C);
 	MFace *mface= NULL;
 	MVert *mvert= NULL;
 	int i, totface, intersect=0;
@@ -3495,6 +3622,110 @@ static int particle_intersect_mesh(const bContext *C, Scene *scene, Object *ob,
 	return intersect;
 }
 
+typedef struct BrushAddCountIterData {
+	Depsgraph *depsgraph;
+	Scene *scene;
+	Object *object;
+	Mesh *mesh;
+	PEData *data;
+	ParticleSystemModifierData *psmd;
+	int number;
+	short size;
+	float imat[4][4];
+	ParticleData *add_pars;
+	int num_added;
+} BrushAddCountIterData;
+
+typedef struct BrushAddCountIterTLSData {
+	RNG *rng;
+	int num_added;
+} BrushAddCountIterTLSData;
+
+static void brush_add_count_iter(
+        void *__restrict iter_data_v,
+        const int iter,
+        const ParallelRangeTLS *__restrict tls_v)
+{
+	BrushAddCountIterData *iter_data = (BrushAddCountIterData *)iter_data_v;
+	Depsgraph *depsgraph = iter_data->depsgraph;
+	PEData *data = iter_data->data;
+	PTCacheEdit *edit = data->edit;
+	ParticleSystem *psys = edit->psys;
+	ParticleSystemModifierData *psmd = iter_data->psmd;
+	ParticleData *add_pars = iter_data->add_pars;
+	BrushAddCountIterTLSData *tls = tls_v->userdata_chunk;
+	const int number = iter_data->number;
+	const short size = iter_data->size;
+	const short size2 = size*size;
+	float dmx, dmy;
+	if (number > 1) {
+		dmx = size;
+		dmy = size;
+		if (tls->rng == NULL) {
+			tls->rng = BLI_rng_new_srandom(
+			        psys->seed + data->mval[0] + data->mval[1] + tls_v->thread_id);
+		}
+		/* rejection sampling to get points in circle */
+		while (dmx*dmx + dmy*dmy > size2) {
+			dmx = (2.0f*BLI_rng_get_float(tls->rng) - 1.0f)*size;
+			dmy = (2.0f*BLI_rng_get_float(tls->rng) - 1.0f)*size;
+		}
+	}
+	else {
+		dmx = 0.0f;
+		dmy = 0.0f;
+	}
+
+	float mco[2];
+	mco[0] = data->mval[0] + dmx;
+	mco[1] = data->mval[1] + dmy;
+
+	float co1[3], co2[3];
+	ED_view3d_win_to_segment(depsgraph, data->vc.ar, data->vc.v3d, mco, co1, co2, true);
+
+	mul_m4_v3(iter_data->imat, co1);
+	mul_m4_v3(iter_data->imat, co2);
+	float min_d = 2.0;
+
+	/* warning, returns the derived mesh face */
+	BLI_assert(iter_data->mesh != NULL);
+	if (particle_intersect_mesh(depsgraph, iter_data->scene, iter_data->object, iter_data->mesh,
+	                            0, co1, co2,
+	                            &min_d,
+	                            &add_pars[iter].num_dmcache,
+	                            add_pars[iter].fuv,
+	                            0, 0, 0, 0)) {
+		if (psys->part->use_modifier_stack && !psmd->mesh_final->runtime.deformed_only) {
+			add_pars[iter].num = add_pars[iter].num_dmcache;
+			add_pars[iter].num_dmcache = DMCACHE_ISCHILD;
+		}
+		else if (iter_data->mesh == psmd->mesh_original) {
+			/* Final DM is not same topology as orig mesh, we have to map num_dmcache to real final dm. */
+			add_pars[iter].num = add_pars[iter].num_dmcache;
+			add_pars[iter].num_dmcache = psys_particle_dm_face_lookup(
+			                              psmd->mesh_final, psmd->mesh_original,
+			                              add_pars[iter].num, add_pars[iter].fuv, NULL);
+		}
+		else {
+			add_pars[iter].num = add_pars[iter].num_dmcache;
+		}
+		if (add_pars[iter].num != DMCACHE_NOTFOUND) {
+			tls->num_added++;
+		}
+	}
+}
+
+static void brush_add_count_iter_finalize(void *__restrict userdata_v,
+                                          void *__restrict userdata_chunk_v)
+{
+	BrushAddCountIterData *iter_data = (BrushAddCountIterData *)userdata_v;
+	BrushAddCountIterTLSData *tls = (BrushAddCountIterTLSData *)userdata_chunk_v;
+	iter_data->num_added += tls->num_added;
+	if (tls->rng != NULL) {
+		BLI_rng_free(tls->rng);
+	}
+}
+
 static int brush_add(const bContext *C, PEData *data, short number)
 {
 	Depsgraph *depsgraph = CTX_data_depsgraph(C);
@@ -3508,12 +3739,9 @@ static int brush_add(const bContext *C, PEData *data, short number)
 	ParticleSimulationData sim= {0};
 	ParticleEditSettings *pset= PE_settings(scene);
 	int i, k, n= 0, totpart= psys->totpart;
-	float mco[2];
-	float dmx, dmy;
-	float co1[3], co2[3], min_d, imat[4][4];
+	float co1[3], imat[4][4];
 	float framestep, timestep;
 	short size= pset->brush[PE_BRUSH_ADD].size;
-	short size2= size*size;
 	RNG *rng;
 
 	invert_m4_m4(imat, ob->obmat);
@@ -3526,12 +3754,12 @@ static int brush_add(const bContext *C, PEData *data, short number)
 	rng = BLI_rng_new_srandom(psys->seed+data->mval[0]+data->mval[1]);
 
 	sim.depsgraph = depsgraph;
-	sim.scene= scene;
-	sim.ob= ob;
-	sim.psys= psys;
-	sim.psmd= psmd;
+	sim.scene = scene;
+	sim.ob = ob;
+	sim.psys = psys;
+	sim.psmd = psmd;
 
-	timestep= psys_get_timestep(&sim);
+	timestep = psys_get_timestep(&sim);
 
 	if (psys->part->use_modifier_stack || psmd->mesh_final->runtime.deformed_only) {
 		mesh = psmd->mesh_final;
@@ -3541,52 +3769,51 @@ static int brush_add(const bContext *C, PEData *data, short number)
 	}
 	BLI_assert(mesh);
 
-	for (i=0; i<number; i++) {
-		if (number>1) {
-			dmx = size;
-			dmy = size;
-
-			/* rejection sampling to get points in circle */
-			while (dmx*dmx + dmy*dmy > size2) {
-				dmx= (2.0f*BLI_rng_get_float(rng) - 1.0f)*size;
-				dmy= (2.0f*BLI_rng_get_float(rng) - 1.0f)*size;
-			}
-		}
-		else {
-			dmx = 0.0f;
-			dmy = 0.0f;
+	/* Calculate positions of new particles to add, based on brush interseciton
+	 * with object. New particle data is assigned to a correponding to check
+	 * index element of add_pars array. This means, that add_pars is a sparse
+	 * array.
+	 */
+	BrushAddCountIterData iter_data;
+	iter_data.depsgraph = depsgraph;
+	iter_data.scene = scene;
+	iter_data.object = ob;
+	iter_data.mesh = mesh;
+	iter_data.data = data;
+	iter_data.psmd = psmd;
+	iter_data.number = number;
+	iter_data.size = size;
+	iter_data.add_pars = add_pars;
+	iter_data.num_added = 0;
+	copy_m4_m4(iter_data.imat, imat);
+
+	BrushAddCountIterTLSData tls = {NULL};
+
+	ParallelRangeSettings settings;
+	BLI_parallel_range_settings_defaults(&settings);
+	settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
+	settings.userdata_chunk = &tls;
+	settings.userdata_chunk_size = sizeof(BrushAddCountIterTLSData);
+	settings.func_finalize = brush_add_count_iter_finalize;
+	BLI_task_parallel_range(0, number, &iter_data, brush_add_count_iter, &settings);
+
+	/* Convert add_parse to a dense array, where all new particles are in the
+	 * beginnign of the array.
+	 */
+	n = iter_data.num_added;
+	for (int current_iter = 0, new_index = 0; current_iter < number; current_iter++) {
+		if (add_pars[current_iter].num == DMCACHE_NOTFOUND) {
+			continue;
 		}
-
-		mco[0] = data->mval[0] + dmx;
-		mco[1] = data->mval[1] + dmy;
-		ED_view3d_win_to_segment(depsgraph, data->vc.ar, data->vc.v3d, mco, co1, co2, true);
-
-		mul_m4_v3(imat, co1);
-		mul_m4_v3(imat, co2);
-		min_d=2.0;
-
-		/* warning, returns the derived mesh face */
-		if (particle_intersect_mesh(C, scene, ob, mesh, 0, co1, co2, &min_d, &add_pars[n].num_dmcache, add_pars[n].fuv, 0, 0, 0, 0)) {
-			if (psys->part->use_modifier_stack && !psmd->mesh_final->runtime.deformed_only) {
-				add_pars[n].num = add_pars[n].num_dmcache;
-				add_pars[n].num_dmcache = DMCACHE_ISCHILD;
-			}
-			else if (mesh == psmd->mesh_original) {
-				/* Final DM is not same topology as orig mesh, we have to map num_dmcache to real final dm. */
-				add_pars[n].num = add_pars[n].num_dmcache;
-				add_pars[n].num_dmcache = psys_particle_dm_face_lookup(
-				                              psmd->mesh_final, psmd->mesh_original,
-				                              add_pars[n].num, add_pars[n].fuv, NULL);
-			}
-			else {
-				add_pars[n].num = add_pars[n].num_dmcache;
-			}
-
-			if (add_pars[n].num != DMCACHE_NOTFOUND) {
-				n++;
-			}
+		if (new_index != current_iter) {
+			new_index++;
+			continue;
 		}
+		memcpy(add_pars + new_index, add_pars + current_iter, sizeof(ParticleData));
+		new_index++;
 	}
+
+	/* TODO(sergey): Consider multi-threading this part as well. */
 	if (n) {
 		int newtotpart=totpart+n;
 		float hairmat[4][4], cur_co[3];