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