Cleanup: style, use braces for blenkernel
[blender.git] / source / blender / blenkernel / intern / particle_distribute.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2007 by Janne Karhu.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bke
22  */
23
24 #include <string.h>
25
26 #include "MEM_guardedalloc.h"
27
28 #include "BLI_utildefines.h"
29 #include "BLI_jitter_2d.h"
30 #include "BLI_kdtree.h"
31 #include "BLI_math.h"
32 #include "BLI_math_geom.h"
33 #include "BLI_rand.h"
34 #include "BLI_sort.h"
35 #include "BLI_task.h"
36
37 #include "DNA_mesh_types.h"
38 #include "DNA_meshdata_types.h"
39 #include "DNA_modifier_types.h"
40 #include "DNA_particle_types.h"
41 #include "DNA_scene_types.h"
42
43 #include "BKE_global.h"
44 #include "BKE_library.h"
45 #include "BKE_mesh.h"
46 #include "BKE_object.h"
47 #include "BKE_particle.h"
48
49 #include "DEG_depsgraph_query.h"
50
51 static void alloc_child_particles(ParticleSystem *psys, int tot)
52 {
53   if (psys->child) {
54     /* only re-allocate if we have to */
55     if (psys->part->childtype && psys->totchild == tot) {
56       memset(psys->child, 0, tot * sizeof(ChildParticle));
57       return;
58     }
59
60     MEM_freeN(psys->child);
61     psys->child = NULL;
62     psys->totchild = 0;
63   }
64
65   if (psys->part->childtype) {
66     psys->totchild = tot;
67     if (psys->totchild) {
68       psys->child = MEM_callocN(psys->totchild * sizeof(ChildParticle), "child_particles");
69     }
70   }
71 }
72
73 static void distribute_simple_children(Scene *scene,
74                                        Object *ob,
75                                        Mesh *final_mesh,
76                                        Mesh *deform_mesh,
77                                        ParticleSystem *psys,
78                                        const bool use_render_params)
79 {
80   ChildParticle *cpa = NULL;
81   int i, p;
82   int child_nbr = psys_get_child_number(scene, psys, use_render_params);
83   int totpart = psys_get_tot_child(scene, psys, use_render_params);
84   RNG *rng = BLI_rng_new_srandom(31415926 + psys->seed + psys->child_seed);
85
86   alloc_child_particles(psys, totpart);
87
88   cpa = psys->child;
89   for (i = 0; i < child_nbr; i++) {
90     for (p = 0; p < psys->totpart; p++, cpa++) {
91       float length = 2.0;
92       cpa->parent = p;
93
94       /* create even spherical distribution inside unit sphere */
95       while (length >= 1.0f) {
96         cpa->fuv[0] = 2.0f * BLI_rng_get_float(rng) - 1.0f;
97         cpa->fuv[1] = 2.0f * BLI_rng_get_float(rng) - 1.0f;
98         cpa->fuv[2] = 2.0f * BLI_rng_get_float(rng) - 1.0f;
99         length = len_v3(cpa->fuv);
100       }
101
102       cpa->num = -1;
103     }
104   }
105   /* dmcache must be updated for parent particles if children from faces is used */
106   psys_calc_dmcache(ob, final_mesh, deform_mesh, psys);
107
108   BLI_rng_free(rng);
109 }
110 static void distribute_grid(Mesh *mesh, ParticleSystem *psys)
111 {
112   ParticleData *pa = NULL;
113   float min[3], max[3], delta[3], d;
114   MVert *mv, *mvert = mesh->mvert;
115   int totvert = mesh->totvert, from = psys->part->from;
116   int i, j, k, p, res = psys->part->grid_res, size[3], axis;
117
118   /* find bounding box of dm */
119   if (totvert > 0) {
120     mv = mvert;
121     copy_v3_v3(min, mv->co);
122     copy_v3_v3(max, mv->co);
123     mv++;
124     for (i = 1; i < totvert; i++, mv++) {
125       minmax_v3v3_v3(min, max, mv->co);
126     }
127   }
128   else {
129     zero_v3(min);
130     zero_v3(max);
131   }
132
133   sub_v3_v3v3(delta, max, min);
134
135   /* determine major axis */
136   axis = axis_dominant_v3_single(delta);
137
138   d = delta[axis] / (float)res;
139
140   size[axis] = res;
141   size[(axis + 1) % 3] = (int)ceil(delta[(axis + 1) % 3] / d);
142   size[(axis + 2) % 3] = (int)ceil(delta[(axis + 2) % 3] / d);
143
144   /* float errors grrr.. */
145   size[(axis + 1) % 3] = MIN2(size[(axis + 1) % 3], res);
146   size[(axis + 2) % 3] = MIN2(size[(axis + 2) % 3], res);
147
148   size[0] = MAX2(size[0], 1);
149   size[1] = MAX2(size[1], 1);
150   size[2] = MAX2(size[2], 1);
151
152   /* no full offset for flat/thin objects */
153   min[0] += d < delta[0] ? d / 2.f : delta[0] / 2.f;
154   min[1] += d < delta[1] ? d / 2.f : delta[1] / 2.f;
155   min[2] += d < delta[2] ? d / 2.f : delta[2] / 2.f;
156
157   for (i = 0, p = 0, pa = psys->particles; i < res; i++) {
158     for (j = 0; j < res; j++) {
159       for (k = 0; k < res; k++, p++, pa++) {
160         pa->fuv[0] = min[0] + (float)i * d;
161         pa->fuv[1] = min[1] + (float)j * d;
162         pa->fuv[2] = min[2] + (float)k * d;
163         pa->flag |= PARS_UNEXIST;
164         pa->hair_index = 0; /* abused in volume calculation */
165       }
166     }
167   }
168
169   /* enable particles near verts/edges/faces/inside surface */
170   if (from == PART_FROM_VERT) {
171     float vec[3];
172
173     pa = psys->particles;
174
175     min[0] -= d / 2.0f;
176     min[1] -= d / 2.0f;
177     min[2] -= d / 2.0f;
178
179     for (i = 0, mv = mvert; i < totvert; i++, mv++) {
180       sub_v3_v3v3(vec, mv->co, min);
181       vec[0] /= delta[0];
182       vec[1] /= delta[1];
183       vec[2] /= delta[2];
184       pa[((int)(vec[0] * (size[0] - 1)) * res + (int)(vec[1] * (size[1] - 1))) * res +
185          (int)(vec[2] * (size[2] - 1))]
186           .flag &= ~PARS_UNEXIST;
187     }
188   }
189   else if (ELEM(from, PART_FROM_FACE, PART_FROM_VOLUME)) {
190     float co1[3], co2[3];
191
192     MFace *mface = NULL, *mface_array;
193     float v1[3], v2[3], v3[3], v4[4], lambda;
194     int a, a1, a2, a0mul, a1mul, a2mul, totface;
195     int amax = from == PART_FROM_FACE ? 3 : 1;
196
197     totface = mesh->totface;
198     mface = mface_array = mesh->mface;
199
200     for (a = 0; a < amax; a++) {
201       if (a == 0) {
202         a0mul = res * res;
203         a1mul = res;
204         a2mul = 1;
205       }
206       else if (a == 1) {
207         a0mul = res;
208         a1mul = 1;
209         a2mul = res * res;
210       }
211       else {
212         a0mul = 1;
213         a1mul = res * res;
214         a2mul = res;
215       }
216
217       for (a1 = 0; a1 < size[(a + 1) % 3]; a1++) {
218         for (a2 = 0; a2 < size[(a + 2) % 3]; a2++) {
219           mface = mface_array;
220
221           pa = psys->particles + a1 * a1mul + a2 * a2mul;
222           copy_v3_v3(co1, pa->fuv);
223           co1[a] -= d < delta[a] ? d / 2.f : delta[a] / 2.f;
224           copy_v3_v3(co2, co1);
225           co2[a] += delta[a] + 0.001f * d;
226           co1[a] -= 0.001f * d;
227
228           struct IsectRayPrecalc isect_precalc;
229           float ray_direction[3];
230           sub_v3_v3v3(ray_direction, co2, co1);
231           isect_ray_tri_watertight_v3_precalc(&isect_precalc, ray_direction);
232
233           /* lets intersect the faces */
234           for (i = 0; i < totface; i++, mface++) {
235             copy_v3_v3(v1, mvert[mface->v1].co);
236             copy_v3_v3(v2, mvert[mface->v2].co);
237             copy_v3_v3(v3, mvert[mface->v3].co);
238
239             bool intersects_tri = isect_ray_tri_watertight_v3(
240                 co1, &isect_precalc, v1, v2, v3, &lambda, NULL);
241             if (intersects_tri) {
242               if (from == PART_FROM_FACE) {
243                 (pa + (int)(lambda * size[a]) * a0mul)->flag &= ~PARS_UNEXIST;
244               }
245               else { /* store number of intersections */
246                 (pa + (int)(lambda * size[a]) * a0mul)->hair_index++;
247               }
248             }
249
250             if (mface->v4 && (!intersects_tri || from == PART_FROM_VOLUME)) {
251               copy_v3_v3(v4, mvert[mface->v4].co);
252
253               if (isect_ray_tri_watertight_v3(co1, &isect_precalc, v1, v3, v4, &lambda, NULL)) {
254                 if (from == PART_FROM_FACE) {
255                   (pa + (int)(lambda * size[a]) * a0mul)->flag &= ~PARS_UNEXIST;
256                 }
257                 else {
258                   (pa + (int)(lambda * size[a]) * a0mul)->hair_index++;
259                 }
260               }
261             }
262           }
263
264           if (from == PART_FROM_VOLUME) {
265             int in = pa->hair_index % 2;
266             if (in) {
267               pa->hair_index++;
268             }
269             for (i = 0; i < size[0]; i++) {
270               if (in || (pa + i * a0mul)->hair_index % 2) {
271                 (pa + i * a0mul)->flag &= ~PARS_UNEXIST;
272               }
273               /* odd intersections == in->out / out->in */
274               /* even intersections -> in stays same */
275               in = (in + (pa + i * a0mul)->hair_index) % 2;
276             }
277           }
278         }
279       }
280     }
281   }
282
283   if (psys->part->flag & PART_GRID_HEXAGONAL) {
284     for (i = 0, p = 0, pa = psys->particles; i < res; i++) {
285       for (j = 0; j < res; j++) {
286         for (k = 0; k < res; k++, p++, pa++) {
287           if (j % 2) {
288             pa->fuv[0] += d / 2.f;
289           }
290
291           if (k % 2) {
292             pa->fuv[0] += d / 2.f;
293             pa->fuv[1] += d / 2.f;
294           }
295         }
296       }
297     }
298   }
299
300   if (psys->part->flag & PART_GRID_INVERT) {
301     for (i = 0; i < size[0]; i++) {
302       for (j = 0; j < size[1]; j++) {
303         pa = psys->particles + res * (i * res + j);
304         for (k = 0; k < size[2]; k++, pa++) {
305           pa->flag ^= PARS_UNEXIST;
306         }
307       }
308     }
309   }
310
311   if (psys->part->grid_rand > 0.f) {
312     float rfac = d * psys->part->grid_rand;
313     for (p = 0, pa = psys->particles; p < psys->totpart; p++, pa++) {
314       if (pa->flag & PARS_UNEXIST) {
315         continue;
316       }
317
318       pa->fuv[0] += rfac * (psys_frand(psys, p + 31) - 0.5f);
319       pa->fuv[1] += rfac * (psys_frand(psys, p + 32) - 0.5f);
320       pa->fuv[2] += rfac * (psys_frand(psys, p + 33) - 0.5f);
321     }
322   }
323 }
324
325 /* modified copy from rayshade.c */
326 static void hammersley_create(float *out, int n, int seed, float amount)
327 {
328   RNG *rng;
329
330   double offs[2], t;
331
332   rng = BLI_rng_new(31415926 + n + seed);
333   offs[0] = BLI_rng_get_double(rng) + (double)amount;
334   offs[1] = BLI_rng_get_double(rng) + (double)amount;
335   BLI_rng_free(rng);
336
337   for (int k = 0; k < n; k++) {
338     BLI_hammersley_1d(k, &t);
339
340     out[2 * k + 0] = fmod((double)k / (double)n + offs[0], 1.0);
341     out[2 * k + 1] = fmod(t + offs[1], 1.0);
342   }
343 }
344
345 /* almost exact copy of BLI_jitter_init */
346 static void init_mv_jit(float *jit, int num, int seed2, float amount)
347 {
348   RNG *rng;
349   float *jit2, x, rad1, rad2, rad3;
350   int i, num2;
351
352   if (num == 0) {
353     return;
354   }
355
356   rad1 = (float)(1.0f / sqrtf((float)num));
357   rad2 = (float)(1.0f / ((float)num));
358   rad3 = (float)sqrtf((float)num) / ((float)num);
359
360   rng = BLI_rng_new(31415926 + num + seed2);
361   x = 0;
362   num2 = 2 * num;
363   for (i = 0; i < num2; i += 2) {
364
365     jit[i] = x + amount * rad1 * (0.5f - BLI_rng_get_float(rng));
366     jit[i + 1] = i / (2.0f * num) + amount * rad1 * (0.5f - BLI_rng_get_float(rng));
367
368     jit[i] -= (float)floor(jit[i]);
369     jit[i + 1] -= (float)floor(jit[i + 1]);
370
371     x += rad3;
372     x -= (float)floor(x);
373   }
374
375   jit2 = MEM_mallocN(12 + 2 * sizeof(float) * num, "initjit");
376
377   for (i = 0; i < 4; i++) {
378     BLI_jitterate1((float(*)[2])jit, (float(*)[2])jit2, num, rad1);
379     BLI_jitterate1((float(*)[2])jit, (float(*)[2])jit2, num, rad1);
380     BLI_jitterate2((float(*)[2])jit, (float(*)[2])jit2, num, rad2);
381   }
382   MEM_freeN(jit2);
383   BLI_rng_free(rng);
384 }
385
386 static void psys_uv_to_w(float u, float v, int quad, float *w)
387 {
388   float vert[4][3], co[3];
389
390   if (!quad) {
391     if (u + v > 1.0f) {
392       v = 1.0f - v;
393     }
394     else {
395       u = 1.0f - u;
396     }
397   }
398
399   vert[0][0] = 0.0f;
400   vert[0][1] = 0.0f;
401   vert[0][2] = 0.0f;
402   vert[1][0] = 1.0f;
403   vert[1][1] = 0.0f;
404   vert[1][2] = 0.0f;
405   vert[2][0] = 1.0f;
406   vert[2][1] = 1.0f;
407   vert[2][2] = 0.0f;
408
409   co[0] = u;
410   co[1] = v;
411   co[2] = 0.0f;
412
413   if (quad) {
414     vert[3][0] = 0.0f;
415     vert[3][1] = 1.0f;
416     vert[3][2] = 0.0f;
417     interp_weights_poly_v3(w, vert, 4, co);
418   }
419   else {
420     interp_weights_poly_v3(w, vert, 3, co);
421     w[3] = 0.0f;
422   }
423 }
424
425 /* Find the index in "sum" array before "value" is crossed. */
426 static int distribute_binary_search(float *sum, int n, float value)
427 {
428   int mid, low = 0, high = n - 1;
429
430   if (high == low) {
431     return low;
432   }
433
434   if (sum[low] >= value) {
435     return low;
436   }
437
438   if (sum[high - 1] < value) {
439     return high;
440   }
441
442   while (low < high) {
443     mid = (low + high) / 2;
444
445     if ((sum[mid] >= value) && (sum[mid - 1] < value)) {
446       return mid;
447     }
448
449     if (sum[mid] > value) {
450       high = mid - 1;
451     }
452     else {
453       low = mid + 1;
454     }
455   }
456
457   return low;
458 }
459
460 /* the max number if calls to rng_* funcs within psys_thread_distribute_particle
461  * be sure to keep up to date if this changes */
462 #define PSYS_RND_DIST_SKIP 3
463
464 /* note: this function must be thread safe, for from == PART_FROM_CHILD */
465 #define ONLY_WORKING_WITH_PA_VERTS 0
466 static void distribute_from_verts_exec(ParticleTask *thread, ParticleData *pa, int p)
467 {
468   ParticleThreadContext *ctx = thread->ctx;
469   MFace *mface;
470
471   mface = ctx->mesh->mface;
472
473   int rng_skip_tot = PSYS_RND_DIST_SKIP; /* count how many rng_* calls wont need skipping */
474
475   /* TODO_PARTICLE - use original index */
476   pa->num = ctx->index[p];
477
478   zero_v4(pa->fuv);
479
480   if (pa->num != DMCACHE_NOTFOUND && pa->num < ctx->mesh->totvert) {
481
482     /* This finds the first face to contain the emitting vertex,
483      * this is not ideal, but is mostly fine as UV seams generally
484      * map to equal-colored parts of a texture */
485     for (int i = 0; i < ctx->mesh->totface; i++, mface++) {
486       if (ELEM(pa->num, mface->v1, mface->v2, mface->v3, mface->v4)) {
487         unsigned int *vert = &mface->v1;
488
489         for (int j = 0; j < 4; j++, vert++) {
490           if (*vert == pa->num) {
491             pa->fuv[j] = 1.0f;
492             break;
493           }
494         }
495
496         break;
497       }
498     }
499   }
500
501 #if ONLY_WORKING_WITH_PA_VERTS
502   if (ctx->tree) {
503     KDTreeNearest_3d ptn[3];
504     int w, maxw;
505
506     psys_particle_on_dm(
507         ctx->mesh, from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, co1, 0, 0, 0, orco1, 0);
508     BKE_mesh_orco_verts_transform(ob->data, &orco1, 1, 1);
509     maxw = BLI_kdtree_3d_find_nearest_n(ctx->tree, orco1, ptn, 3);
510
511     for (w = 0; w < maxw; w++) {
512       pa->verts[w] = ptn->num;
513     }
514   }
515 #endif
516
517   BLI_assert(rng_skip_tot >= 0); /* should never be below zero */
518   if (rng_skip_tot > 0) {
519     BLI_rng_skip(thread->rng, rng_skip_tot);
520   }
521 }
522
523 static void distribute_from_faces_exec(ParticleTask *thread, ParticleData *pa, int p)
524 {
525   ParticleThreadContext *ctx = thread->ctx;
526   Mesh *mesh = ctx->mesh;
527   float randu, randv;
528   int distr = ctx->distr;
529   int i;
530   int rng_skip_tot = PSYS_RND_DIST_SKIP; /* count how many rng_* calls wont need skipping */
531
532   MFace *mface;
533
534   pa->num = i = ctx->index[p];
535   mface = &mesh->mface[i];
536
537   switch (distr) {
538     case PART_DISTR_JIT:
539       if (ctx->jitlevel == 1) {
540         if (mface->v4) {
541           psys_uv_to_w(0.5f, 0.5f, mface->v4, pa->fuv);
542         }
543         else {
544           psys_uv_to_w(1.0f / 3.0f, 1.0f / 3.0f, mface->v4, pa->fuv);
545         }
546       }
547       else {
548         float offset = fmod(ctx->jitoff[i] + (float)p, (float)ctx->jitlevel);
549         if (!isnan(offset)) {
550           psys_uv_to_w(
551               ctx->jit[2 * (int)offset], ctx->jit[2 * (int)offset + 1], mface->v4, pa->fuv);
552         }
553       }
554       break;
555     case PART_DISTR_RAND:
556       randu = BLI_rng_get_float(thread->rng);
557       randv = BLI_rng_get_float(thread->rng);
558       rng_skip_tot -= 2;
559
560       psys_uv_to_w(randu, randv, mface->v4, pa->fuv);
561       break;
562   }
563   pa->foffset = 0.0f;
564
565   BLI_assert(rng_skip_tot >= 0); /* should never be below zero */
566   if (rng_skip_tot > 0) {
567     BLI_rng_skip(thread->rng, rng_skip_tot);
568   }
569 }
570
571 static void distribute_from_volume_exec(ParticleTask *thread, ParticleData *pa, int p)
572 {
573   ParticleThreadContext *ctx = thread->ctx;
574   Mesh *mesh = ctx->mesh;
575   float *v1, *v2, *v3, *v4, nor[3], co[3];
576   float cur_d, min_d, randu, randv;
577   int distr = ctx->distr;
578   int i, intersect, tot;
579   int rng_skip_tot = PSYS_RND_DIST_SKIP; /* count how many rng_* calls wont need skipping */
580
581   MFace *mface;
582   MVert *mvert = mesh->mvert;
583
584   pa->num = i = ctx->index[p];
585   mface = &mesh->mface[i];
586
587   switch (distr) {
588     case PART_DISTR_JIT:
589       if (ctx->jitlevel == 1) {
590         if (mface->v4) {
591           psys_uv_to_w(0.5f, 0.5f, mface->v4, pa->fuv);
592         }
593         else {
594           psys_uv_to_w(1.0f / 3.0f, 1.0f / 3.0f, mface->v4, pa->fuv);
595         }
596       }
597       else {
598         float offset = fmod(ctx->jitoff[i] + (float)p, (float)ctx->jitlevel);
599         if (!isnan(offset)) {
600           psys_uv_to_w(
601               ctx->jit[2 * (int)offset], ctx->jit[2 * (int)offset + 1], mface->v4, pa->fuv);
602         }
603       }
604       break;
605     case PART_DISTR_RAND:
606       randu = BLI_rng_get_float(thread->rng);
607       randv = BLI_rng_get_float(thread->rng);
608       rng_skip_tot -= 2;
609
610       psys_uv_to_w(randu, randv, mface->v4, pa->fuv);
611       break;
612   }
613   pa->foffset = 0.0f;
614
615   /* experimental */
616   tot = mesh->totface;
617
618   psys_interpolate_face(mvert, mface, 0, 0, pa->fuv, co, nor, 0, 0, 0);
619
620   normalize_v3(nor);
621   negate_v3(nor);
622
623   min_d = FLT_MAX;
624   intersect = 0;
625
626   for (i = 0, mface = mesh->mface; i < tot; i++, mface++) {
627     if (i == pa->num) {
628       continue;
629     }
630
631     v1 = mvert[mface->v1].co;
632     v2 = mvert[mface->v2].co;
633     v3 = mvert[mface->v3].co;
634
635     if (isect_ray_tri_v3(co, nor, v2, v3, v1, &cur_d, NULL)) {
636       if (cur_d < min_d) {
637         min_d = cur_d;
638         pa->foffset = cur_d * 0.5f; /* to the middle of volume */
639         intersect = 1;
640       }
641     }
642     if (mface->v4) {
643       v4 = mvert[mface->v4].co;
644
645       if (isect_ray_tri_v3(co, nor, v4, v1, v3, &cur_d, NULL)) {
646         if (cur_d < min_d) {
647           min_d = cur_d;
648           pa->foffset = cur_d * 0.5f; /* to the middle of volume */
649           intersect = 1;
650         }
651       }
652     }
653   }
654   if (intersect == 0) {
655     pa->foffset = 0.0;
656   }
657   else {
658     switch (distr) {
659       case PART_DISTR_JIT:
660         pa->foffset *= ctx->jit[p % (2 * ctx->jitlevel)];
661         break;
662       case PART_DISTR_RAND:
663         pa->foffset *= BLI_rng_get_float(thread->rng);
664         rng_skip_tot--;
665         break;
666     }
667   }
668
669   BLI_assert(rng_skip_tot >= 0); /* should never be below zero */
670   if (rng_skip_tot > 0) {
671     BLI_rng_skip(thread->rng, rng_skip_tot);
672   }
673 }
674
675 static void distribute_children_exec(ParticleTask *thread, ChildParticle *cpa, int p)
676 {
677   ParticleThreadContext *ctx = thread->ctx;
678   Object *ob = ctx->sim.ob;
679   Mesh *mesh = ctx->mesh;
680   float orco1[3], co1[3], nor1[3];
681   float randu, randv;
682   int cfrom = ctx->cfrom;
683   int i;
684   int rng_skip_tot = PSYS_RND_DIST_SKIP; /* count how many rng_* calls wont need skipping */
685
686   MFace *mf;
687
688   if (ctx->index[p] < 0) {
689     cpa->num = 0;
690     cpa->fuv[0] = cpa->fuv[1] = cpa->fuv[2] = cpa->fuv[3] = 0.0f;
691     cpa->pa[0] = cpa->pa[1] = cpa->pa[2] = cpa->pa[3] = 0;
692     return;
693   }
694
695   mf = &mesh->mface[ctx->index[p]];
696
697   randu = BLI_rng_get_float(thread->rng);
698   randv = BLI_rng_get_float(thread->rng);
699   rng_skip_tot -= 2;
700
701   psys_uv_to_w(randu, randv, mf->v4, cpa->fuv);
702
703   cpa->num = ctx->index[p];
704
705   if (ctx->tree) {
706     KDTreeNearest_3d ptn[10];
707     int w, maxw;  //, do_seams;
708     float maxd /*, mind,dd */, totw = 0.0f;
709     int parent[10];
710     float pweight[10];
711
712     psys_particle_on_dm(mesh,
713                         cfrom,
714                         cpa->num,
715                         DMCACHE_ISCHILD,
716                         cpa->fuv,
717                         cpa->foffset,
718                         co1,
719                         nor1,
720                         NULL,
721                         NULL,
722                         orco1);
723     BKE_mesh_orco_verts_transform(ob->data, &orco1, 1, 1);
724     maxw = BLI_kdtree_3d_find_nearest_n(ctx->tree, orco1, ptn, 3);
725
726     maxd = ptn[maxw - 1].dist;
727     /* mind=ptn[0].dist; */ /* UNUSED */
728
729     /* the weights here could be done better */
730     for (w = 0; w < maxw; w++) {
731       parent[w] = ptn[w].index;
732       pweight[w] = (float)pow(2.0, (double)(-6.0f * ptn[w].dist / maxd));
733     }
734     for (; w < 10; w++) {
735       parent[w] = -1;
736       pweight[w] = 0.0f;
737     }
738
739     for (w = 0, i = 0; w < maxw && i < 4; w++) {
740       if (parent[w] >= 0) {
741         cpa->pa[i] = parent[w];
742         cpa->w[i] = pweight[w];
743         totw += pweight[w];
744         i++;
745       }
746     }
747     for (; i < 4; i++) {
748       cpa->pa[i] = -1;
749       cpa->w[i] = 0.0f;
750     }
751
752     if (totw > 0.0f) {
753       for (w = 0; w < 4; w++) {
754         cpa->w[w] /= totw;
755       }
756     }
757
758     cpa->parent = cpa->pa[0];
759   }
760
761   if (rng_skip_tot > 0) { /* should never be below zero */
762     BLI_rng_skip(thread->rng, rng_skip_tot);
763   }
764 }
765
766 static void exec_distribute_parent(TaskPool *__restrict UNUSED(pool),
767                                    void *taskdata,
768                                    int UNUSED(threadid))
769 {
770   ParticleTask *task = taskdata;
771   ParticleSystem *psys = task->ctx->sim.psys;
772   ParticleData *pa;
773   int p;
774
775   BLI_rng_skip(task->rng, PSYS_RND_DIST_SKIP * task->begin);
776
777   pa = psys->particles + task->begin;
778   switch (psys->part->from) {
779     case PART_FROM_FACE:
780       for (p = task->begin; p < task->end; ++p, ++pa) {
781         distribute_from_faces_exec(task, pa, p);
782       }
783       break;
784     case PART_FROM_VOLUME:
785       for (p = task->begin; p < task->end; ++p, ++pa) {
786         distribute_from_volume_exec(task, pa, p);
787       }
788       break;
789     case PART_FROM_VERT:
790       for (p = task->begin; p < task->end; ++p, ++pa) {
791         distribute_from_verts_exec(task, pa, p);
792       }
793       break;
794   }
795 }
796
797 static void exec_distribute_child(TaskPool *__restrict UNUSED(pool),
798                                   void *taskdata,
799                                   int UNUSED(threadid))
800 {
801   ParticleTask *task = taskdata;
802   ParticleSystem *psys = task->ctx->sim.psys;
803   ChildParticle *cpa;
804   int p;
805
806   /* RNG skipping at the beginning */
807   cpa = psys->child;
808   for (p = 0; p < task->begin; ++p, ++cpa) {
809     BLI_rng_skip(task->rng, PSYS_RND_DIST_SKIP);
810   }
811
812   for (; p < task->end; ++p, ++cpa) {
813     distribute_children_exec(task, cpa, p);
814   }
815 }
816
817 static int distribute_compare_orig_index(const void *p1, const void *p2, void *user_data)
818 {
819   int *orig_index = (int *)user_data;
820   int index1 = orig_index[*(const int *)p1];
821   int index2 = orig_index[*(const int *)p2];
822
823   if (index1 < index2) {
824     return -1;
825   }
826   else if (index1 == index2) {
827     /* this pointer comparison appears to make qsort stable for glibc,
828      * and apparently on solaris too, makes the renders reproducible */
829     if (p1 < p2) {
830       return -1;
831     }
832     else if (p1 == p2) {
833       return 0;
834     }
835     else {
836       return 1;
837     }
838   }
839   else {
840     return 1;
841   }
842 }
843
844 static void distribute_invalid(ParticleSimulationData *sim, int from)
845 {
846   Scene *scene = sim->scene;
847   ParticleSystem *psys = sim->psys;
848   const bool use_render_params = (DEG_get_mode(sim->depsgraph) == DAG_EVAL_RENDER);
849
850   if (from == PART_FROM_CHILD) {
851     ChildParticle *cpa;
852     int p, totchild = psys_get_tot_child(scene, psys, use_render_params);
853
854     if (psys->child && totchild) {
855       for (p = 0, cpa = psys->child; p < totchild; p++, cpa++) {
856         cpa->fuv[0] = cpa->fuv[1] = cpa->fuv[2] = cpa->fuv[3] = 0.0;
857         cpa->foffset = 0.0f;
858         cpa->parent = 0;
859         cpa->pa[0] = cpa->pa[1] = cpa->pa[2] = cpa->pa[3] = 0;
860         cpa->num = -1;
861       }
862     }
863   }
864   else {
865     PARTICLE_P;
866     LOOP_PARTICLES
867     {
868       pa->fuv[0] = pa->fuv[1] = pa->fuv[2] = pa->fuv[3] = 0.0;
869       pa->foffset = 0.0f;
870       pa->num = -1;
871     }
872   }
873 }
874
875 /* Creates a distribution of coordinates on a Mesh */
876 static int psys_thread_context_init_distribute(ParticleThreadContext *ctx,
877                                                ParticleSimulationData *sim,
878                                                int from)
879 {
880   Scene *scene = sim->scene;
881   Mesh *final_mesh = sim->psmd->mesh_final;
882   Object *ob = sim->ob;
883   ParticleSystem *psys = sim->psys;
884   ParticleData *pa = 0, *tpars = 0;
885   ParticleSettings *part;
886   ParticleSeam *seams = 0;
887   KDTree_3d *tree = 0;
888   Mesh *mesh = NULL;
889   float *jit = NULL;
890   int i, p = 0;
891   int cfrom = 0;
892   int totelem = 0, totpart, *particle_element = 0, children = 0, totseam = 0;
893   int jitlevel = 1, distr;
894   float *element_weight = NULL, *jitter_offset = NULL, *vweight = NULL;
895   float cur, maxweight = 0.0, tweight, totweight, inv_totweight, co[3], nor[3], orco[3];
896   RNG *rng = NULL;
897
898   if (ELEM(NULL, ob, psys, psys->part)) {
899     return 0;
900   }
901
902   part = psys->part;
903   totpart = psys->totpart;
904   if (totpart == 0) {
905     return 0;
906   }
907
908   if (!final_mesh->runtime.deformed_only &&
909       !CustomData_get_layer(&final_mesh->fdata, CD_ORIGINDEX)) {
910     printf(
911         "Can't create particles with the current modifier stack, disable destructive modifiers\n");
912     // XXX      error("Can't paint with the current modifier stack, disable destructive modifiers");
913     return 0;
914   }
915
916   /* XXX This distribution code is totally broken in case from == PART_FROM_CHILD, it's always using finaldm
917    *     even if use_modifier_stack is unset... But making things consistent here break all existing edited
918    *     hair systems, so better wait for complete rewrite.
919    */
920
921   psys_thread_context_init(ctx, sim);
922
923   const bool use_render_params = (DEG_get_mode(sim->depsgraph) == DAG_EVAL_RENDER);
924
925   /* First handle special cases */
926   if (from == PART_FROM_CHILD) {
927     /* Simple children */
928     if (part->childtype != PART_CHILD_FACES) {
929       distribute_simple_children(
930           scene, ob, final_mesh, sim->psmd->mesh_original, psys, use_render_params);
931       return 0;
932     }
933   }
934   else {
935     /* Grid distribution */
936     if (part->distr == PART_DISTR_GRID && from != PART_FROM_VERT) {
937       if (psys->part->use_modifier_stack) {
938         mesh = final_mesh;
939       }
940       else {
941         BKE_id_copy_ex(NULL, ob->data, (ID **)&mesh, LIB_ID_COPY_LOCALIZE);
942       }
943       BKE_mesh_tessface_ensure(mesh);
944
945       distribute_grid(mesh, psys);
946
947       if (mesh != final_mesh) {
948         BKE_id_free(NULL, mesh);
949       }
950
951       return 0;
952     }
953   }
954
955   /* Create trees and original coordinates if needed */
956   if (from == PART_FROM_CHILD) {
957     distr = PART_DISTR_RAND;
958     rng = BLI_rng_new_srandom(31415926 + psys->seed + psys->child_seed);
959     mesh = final_mesh;
960
961     /* BMESH ONLY */
962     BKE_mesh_tessface_ensure(mesh);
963
964     children = 1;
965
966     tree = BLI_kdtree_3d_new(totpart);
967
968     for (p = 0, pa = psys->particles; p < totpart; p++, pa++) {
969       psys_particle_on_dm(
970           mesh, part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, co, nor, 0, 0, orco);
971       BKE_mesh_orco_verts_transform(ob->data, &orco, 1, 1);
972       BLI_kdtree_3d_insert(tree, p, orco);
973     }
974
975     BLI_kdtree_3d_balance(tree);
976
977     totpart = psys_get_tot_child(scene, psys, use_render_params);
978     cfrom = from = PART_FROM_FACE;
979   }
980   else {
981     distr = part->distr;
982
983     rng = BLI_rng_new_srandom(31415926 + psys->seed);
984
985     if (psys->part->use_modifier_stack) {
986       mesh = final_mesh;
987     }
988     else {
989       BKE_id_copy_ex(NULL, ob->data, (ID **)&mesh, LIB_ID_COPY_LOCALIZE);
990     }
991
992     BKE_mesh_tessface_ensure(mesh);
993
994     /* we need orco for consistent distributions */
995     if (!CustomData_has_layer(&mesh->vdata, CD_ORCO)) {
996       /* Orcos are stored in normalized 0..1 range by convention. */
997       float(*orcodata)[3] = BKE_mesh_orco_verts_get(ob);
998       BKE_mesh_orco_verts_transform(mesh, orcodata, mesh->totvert, false);
999       CustomData_add_layer(&mesh->vdata, CD_ORCO, CD_ASSIGN, orcodata, mesh->totvert);
1000     }
1001
1002     if (from == PART_FROM_VERT) {
1003       MVert *mv = mesh->mvert;
1004       float(*orcodata)[3] = CustomData_get_layer(&mesh->vdata, CD_ORCO);
1005       int totvert = mesh->totvert;
1006
1007       tree = BLI_kdtree_3d_new(totvert);
1008
1009       for (p = 0; p < totvert; p++) {
1010         if (orcodata) {
1011           copy_v3_v3(co, orcodata[p]);
1012           BKE_mesh_orco_verts_transform(ob->data, &co, 1, 1);
1013         }
1014         else {
1015           copy_v3_v3(co, mv[p].co);
1016         }
1017         BLI_kdtree_3d_insert(tree, p, co);
1018       }
1019
1020       BLI_kdtree_3d_balance(tree);
1021     }
1022   }
1023
1024   /* Get total number of emission elements and allocate needed arrays */
1025   totelem = (from == PART_FROM_VERT) ? mesh->totvert : mesh->totface;
1026
1027   if (totelem == 0) {
1028     distribute_invalid(sim, children ? PART_FROM_CHILD : 0);
1029
1030     if (G.debug & G_DEBUG) {
1031       fprintf(stderr, "Particle distribution error: Nothing to emit from!\n");
1032     }
1033
1034     if (mesh != final_mesh) {
1035       BKE_id_free(NULL, mesh);
1036     }
1037
1038     BLI_kdtree_3d_free(tree);
1039     BLI_rng_free(rng);
1040
1041     return 0;
1042   }
1043
1044   element_weight = MEM_callocN(sizeof(float) * totelem, "particle_distribution_weights");
1045   particle_element = MEM_callocN(sizeof(int) * totpart, "particle_distribution_indexes");
1046   jitter_offset = MEM_callocN(sizeof(float) * totelem, "particle_distribution_jitoff");
1047
1048   /* Calculate weights from face areas */
1049   if ((part->flag & PART_EDISTR || children) && from != PART_FROM_VERT) {
1050     MVert *v1, *v2, *v3, *v4;
1051     float totarea = 0.f, co1[3], co2[3], co3[3], co4[3];
1052     float(*orcodata)[3];
1053
1054     orcodata = CustomData_get_layer(&mesh->vdata, CD_ORCO);
1055
1056     for (i = 0; i < totelem; i++) {
1057       MFace *mf = &mesh->mface[i];
1058
1059       if (orcodata) {
1060         /* Transform orcos from normalized 0..1 to object space. */
1061         copy_v3_v3(co1, orcodata[mf->v1]);
1062         copy_v3_v3(co2, orcodata[mf->v2]);
1063         copy_v3_v3(co3, orcodata[mf->v3]);
1064         BKE_mesh_orco_verts_transform(ob->data, &co1, 1, 1);
1065         BKE_mesh_orco_verts_transform(ob->data, &co2, 1, 1);
1066         BKE_mesh_orco_verts_transform(ob->data, &co3, 1, 1);
1067         if (mf->v4) {
1068           copy_v3_v3(co4, orcodata[mf->v4]);
1069           BKE_mesh_orco_verts_transform(ob->data, &co4, 1, 1);
1070         }
1071       }
1072       else {
1073         v1 = &mesh->mvert[mf->v1];
1074         v2 = &mesh->mvert[mf->v2];
1075         v3 = &mesh->mvert[mf->v3];
1076         copy_v3_v3(co1, v1->co);
1077         copy_v3_v3(co2, v2->co);
1078         copy_v3_v3(co3, v3->co);
1079         if (mf->v4) {
1080           v4 = &mesh->mvert[mf->v4];
1081           copy_v3_v3(co4, v4->co);
1082         }
1083       }
1084
1085       cur = mf->v4 ? area_quad_v3(co1, co2, co3, co4) : area_tri_v3(co1, co2, co3);
1086
1087       if (cur > maxweight) {
1088         maxweight = cur;
1089       }
1090
1091       element_weight[i] = cur;
1092       totarea += cur;
1093     }
1094
1095     for (i = 0; i < totelem; i++) {
1096       element_weight[i] /= totarea;
1097     }
1098
1099     maxweight /= totarea;
1100   }
1101   else {
1102     float min = 1.0f / (float)(MIN2(totelem, totpart));
1103     for (i = 0; i < totelem; i++) {
1104       element_weight[i] = min;
1105     }
1106     maxweight = min;
1107   }
1108
1109   /* Calculate weights from vgroup */
1110   vweight = psys_cache_vgroup(mesh, psys, PSYS_VG_DENSITY);
1111
1112   if (vweight) {
1113     if (from == PART_FROM_VERT) {
1114       for (i = 0; i < totelem; i++) {
1115         element_weight[i] *= vweight[i];
1116       }
1117     }
1118     else { /* PART_FROM_FACE / PART_FROM_VOLUME */
1119       for (i = 0; i < totelem; i++) {
1120         MFace *mf = &mesh->mface[i];
1121         tweight = vweight[mf->v1] + vweight[mf->v2] + vweight[mf->v3];
1122
1123         if (mf->v4) {
1124           tweight += vweight[mf->v4];
1125           tweight /= 4.0f;
1126         }
1127         else {
1128           tweight /= 3.0f;
1129         }
1130
1131         element_weight[i] *= tweight;
1132       }
1133     }
1134     MEM_freeN(vweight);
1135   }
1136
1137   /* Calculate total weight of all elements */
1138   int totmapped = 0;
1139   totweight = 0.0f;
1140   for (i = 0; i < totelem; i++) {
1141     if (element_weight[i] > 0.0f) {
1142       totmapped++;
1143       totweight += element_weight[i];
1144     }
1145   }
1146
1147   if (totmapped == 0) {
1148     /* We are not allowed to distribute particles anywhere... */
1149     if (mesh != final_mesh) {
1150       BKE_id_free(NULL, mesh);
1151     }
1152     BLI_kdtree_3d_free(tree);
1153     BLI_rng_free(rng);
1154     MEM_freeN(element_weight);
1155     MEM_freeN(particle_element);
1156     MEM_freeN(jitter_offset);
1157     return 0;
1158   }
1159
1160   inv_totweight = 1.0f / totweight;
1161
1162   /* Calculate cumulative weights.
1163    * We remove all null-weighted elements from element_sum, and create a new mapping
1164    * 'activ'_elem_index -> orig_elem_index.
1165    * This simplifies greatly the filtering of zero-weighted items - and can be much more efficient
1166    * especially in random case (reducing a lot the size of binary-searched array)...
1167    */
1168   float *element_sum = MEM_mallocN(sizeof(*element_sum) * totmapped, __func__);
1169   int *element_map = MEM_mallocN(sizeof(*element_map) * totmapped, __func__);
1170   int i_mapped = 0;
1171
1172   for (i = 0; i < totelem && element_weight[i] == 0.0f; i++) {
1173     ;
1174   }
1175   element_sum[i_mapped] = element_weight[i] * inv_totweight;
1176   element_map[i_mapped] = i;
1177   i_mapped++;
1178   for (i++; i < totelem; i++) {
1179     if (element_weight[i] > 0.0f) {
1180       element_sum[i_mapped] = element_sum[i_mapped - 1] + element_weight[i] * inv_totweight;
1181       /* Skip elements which weight is so small that it does not affect the sum. */
1182       if (element_sum[i_mapped] > element_sum[i_mapped - 1]) {
1183         element_map[i_mapped] = i;
1184         i_mapped++;
1185       }
1186     }
1187   }
1188   totmapped = i_mapped;
1189
1190   /* Finally assign elements to particles */
1191   if (part->flag & PART_TRAND) {
1192     for (p = 0; p < totpart; p++) {
1193       /* In theory element_sum[totmapped - 1] should be 1.0,
1194        * but due to float errors this is not necessarily always true, so scale pos accordingly. */
1195       const float pos = BLI_rng_get_float(rng) * element_sum[totmapped - 1];
1196       const int eidx = distribute_binary_search(element_sum, totmapped, pos);
1197       particle_element[p] = element_map[eidx];
1198       BLI_assert(pos <= element_sum[eidx]);
1199       BLI_assert(eidx ? (pos > element_sum[eidx - 1]) : (pos >= 0.0f));
1200       jitter_offset[particle_element[p]] = pos;
1201     }
1202   }
1203   else {
1204     double step, pos;
1205
1206     step = (totpart < 2) ? 0.5 : 1.0 / (double)totpart;
1207     /* This is to address tricky issues with vertex-emitting when user tries (and expects) exact 1-1 vert/part
1208      * distribution (see T47983 and its two example files). It allows us to consider pos as
1209      * 'midpoint between v and v+1' (or 'p and p+1', depending whether we have more vertices than particles or not),
1210      * and avoid stumbling over float impression in element_sum.
1211      * Note: moved face and volume distribution to this as well (instead of starting at zero),
1212      * for the same reasons, see T52682. */
1213     pos = (totpart < totmapped) ? 0.5 / (double)totmapped :
1214                                   step * 0.5; /* We choose the smaller step. */
1215
1216     for (i = 0, p = 0; p < totpart; p++, pos += step) {
1217       for (; (i < totmapped - 1) && (pos > (double)element_sum[i]); i++) {
1218         ;
1219       }
1220
1221       particle_element[p] = element_map[i];
1222
1223       jitter_offset[particle_element[p]] = pos;
1224     }
1225   }
1226
1227   MEM_freeN(element_sum);
1228   MEM_freeN(element_map);
1229
1230   /* For hair, sort by origindex (allows optimization's in rendering), */
1231   /* however with virtual parents the children need to be in random order. */
1232   if (part->type == PART_HAIR && !(part->childtype == PART_CHILD_FACES && part->parents != 0.0f)) {
1233     int *orig_index = NULL;
1234
1235     if (from == PART_FROM_VERT) {
1236       if (mesh->totvert) {
1237         orig_index = CustomData_get_layer(&mesh->vdata, CD_ORIGINDEX);
1238       }
1239     }
1240     else {
1241       if (mesh->totface) {
1242         orig_index = CustomData_get_layer(&mesh->fdata, CD_ORIGINDEX);
1243       }
1244     }
1245
1246     if (orig_index) {
1247       BLI_qsort_r(
1248           particle_element, totpart, sizeof(int), distribute_compare_orig_index, orig_index);
1249     }
1250   }
1251
1252   /* Create jittering if needed */
1253   if (distr == PART_DISTR_JIT && ELEM(from, PART_FROM_FACE, PART_FROM_VOLUME)) {
1254     jitlevel = part->userjit;
1255
1256     if (jitlevel == 0) {
1257       jitlevel = totpart / totelem;
1258       if (part->flag & PART_EDISTR) {
1259         jitlevel *= 2; /* looks better in general, not very scientific */
1260       }
1261       if (jitlevel < 3) {
1262         jitlevel = 3;
1263       }
1264     }
1265
1266     jit = MEM_callocN((2 + jitlevel * 2) * sizeof(float), "jit");
1267
1268     /* for small amounts of particles we use regular jitter since it looks
1269      * a bit better, for larger amounts we switch to hammersley sequence
1270      * because it is much faster */
1271     if (jitlevel < 25) {
1272       init_mv_jit(jit, jitlevel, psys->seed, part->jitfac);
1273     }
1274     else {
1275       hammersley_create(jit, jitlevel + 1, psys->seed, part->jitfac);
1276     }
1277     BLI_array_randomize(
1278         jit, 2 * sizeof(float), jitlevel, psys->seed); /* for custom jit or even distribution */
1279   }
1280
1281   /* Setup things for threaded distribution */
1282   ctx->tree = tree;
1283   ctx->seams = seams;
1284   ctx->totseam = totseam;
1285   ctx->sim.psys = psys;
1286   ctx->index = particle_element;
1287   ctx->jit = jit;
1288   ctx->jitlevel = jitlevel;
1289   ctx->jitoff = jitter_offset;
1290   ctx->weight = element_weight;
1291   ctx->maxweight = maxweight;
1292   ctx->cfrom = cfrom;
1293   ctx->distr = distr;
1294   ctx->mesh = mesh;
1295   ctx->tpars = tpars;
1296
1297   if (children) {
1298     alloc_child_particles(psys, totpart);
1299   }
1300
1301   BLI_rng_free(rng);
1302
1303   return 1;
1304 }
1305
1306 static void psys_task_init_distribute(ParticleTask *task, ParticleSimulationData *sim)
1307 {
1308   /* init random number generator */
1309   int seed = 31415926 + sim->psys->seed;
1310
1311   task->rng = BLI_rng_new(seed);
1312 }
1313
1314 static void distribute_particles_on_dm(ParticleSimulationData *sim, int from)
1315 {
1316   TaskScheduler *task_scheduler;
1317   TaskPool *task_pool;
1318   ParticleThreadContext ctx;
1319   ParticleTask *tasks;
1320   Mesh *final_mesh = sim->psmd->mesh_final;
1321   int i, totpart, numtasks;
1322
1323   /* create a task pool for distribution tasks */
1324   if (!psys_thread_context_init_distribute(&ctx, sim, from)) {
1325     return;
1326   }
1327
1328   task_scheduler = BLI_task_scheduler_get();
1329   task_pool = BLI_task_pool_create(task_scheduler, &ctx);
1330
1331   totpart = (from == PART_FROM_CHILD ? sim->psys->totchild : sim->psys->totpart);
1332   psys_tasks_create(&ctx, 0, totpart, &tasks, &numtasks);
1333   for (i = 0; i < numtasks; ++i) {
1334     ParticleTask *task = &tasks[i];
1335
1336     psys_task_init_distribute(task, sim);
1337     if (from == PART_FROM_CHILD) {
1338       BLI_task_pool_push(task_pool, exec_distribute_child, task, false, TASK_PRIORITY_LOW);
1339     }
1340     else {
1341       BLI_task_pool_push(task_pool, exec_distribute_parent, task, false, TASK_PRIORITY_LOW);
1342     }
1343   }
1344   BLI_task_pool_work_and_wait(task_pool);
1345
1346   BLI_task_pool_free(task_pool);
1347
1348   psys_calc_dmcache(sim->ob, final_mesh, sim->psmd->mesh_original, sim->psys);
1349
1350   if (ctx.mesh != final_mesh) {
1351     BKE_id_free(NULL, ctx.mesh);
1352   }
1353
1354   psys_tasks_free(tasks, numtasks);
1355
1356   psys_thread_context_free(&ctx);
1357 }
1358
1359 /* ready for future use, to emit particles without geometry */
1360 static void distribute_particles_on_shape(ParticleSimulationData *sim, int UNUSED(from))
1361 {
1362   distribute_invalid(sim, 0);
1363
1364   fprintf(stderr, "Shape emission not yet possible!\n");
1365 }
1366
1367 void distribute_particles(ParticleSimulationData *sim, int from)
1368 {
1369   PARTICLE_PSMD;
1370   int distr_error = 0;
1371
1372   if (psmd) {
1373     if (psmd->mesh_final) {
1374       distribute_particles_on_dm(sim, from);
1375     }
1376     else {
1377       distr_error = 1;
1378     }
1379   }
1380   else {
1381     distribute_particles_on_shape(sim, from);
1382   }
1383
1384   if (distr_error) {
1385     distribute_invalid(sim, from);
1386
1387     fprintf(stderr, "Particle distribution error!\n");
1388   }
1389 }