Cleanup: style, use braces for blenkernel
[blender.git] / source / blender / blenkernel / intern / particle.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 <stdlib.h>
25 #include <math.h>
26 #include <string.h>
27
28 #include "MEM_guardedalloc.h"
29
30 #include "DNA_collection_types.h"
31 #include "DNA_curve_types.h"
32 #include "DNA_key_types.h"
33 #include "DNA_material_types.h"
34 #include "DNA_mesh_types.h"
35 #include "DNA_meshdata_types.h"
36 #include "DNA_particle_types.h"
37 #include "DNA_smoke_types.h"
38 #include "DNA_scene_types.h"
39 #include "DNA_dynamicpaint_types.h"
40
41 #include "BLI_blenlib.h"
42 #include "BLI_math.h"
43 #include "BLI_utildefines.h"
44 #include "BLI_kdopbvh.h"
45 #include "BLI_kdtree.h"
46 #include "BLI_rand.h"
47 #include "BLI_task.h"
48 #include "BLI_threads.h"
49 #include "BLI_linklist.h"
50
51 #include "BLT_translation.h"
52
53 #include "BKE_anim.h"
54 #include "BKE_animsys.h"
55
56 #include "BKE_boids.h"
57 #include "BKE_cloth.h"
58 #include "BKE_collection.h"
59 #include "BKE_colortools.h"
60 #include "BKE_effect.h"
61 #include "BKE_main.h"
62 #include "BKE_lattice.h"
63
64 #include "BKE_displist.h"
65 #include "BKE_particle.h"
66 #include "BKE_material.h"
67 #include "BKE_key.h"
68 #include "BKE_library.h"
69 #include "BKE_modifier.h"
70 #include "BKE_mesh.h"
71 #include "BKE_cdderivedmesh.h" /* for weight_to_rgb() */
72 #include "BKE_pointcache.h"
73 #include "BKE_scene.h"
74 #include "BKE_deform.h"
75
76 #include "DEG_depsgraph.h"
77 #include "DEG_depsgraph_build.h"
78 #include "DEG_depsgraph_query.h"
79
80 #include "RE_render_ext.h"
81
82 #include "particle_private.h"
83
84 unsigned int PSYS_FRAND_SEED_OFFSET[PSYS_FRAND_COUNT];
85 unsigned int PSYS_FRAND_SEED_MULTIPLIER[PSYS_FRAND_COUNT];
86 float PSYS_FRAND_BASE[PSYS_FRAND_COUNT];
87
88 void psys_init_rng(void)
89 {
90   RNG *rng = BLI_rng_new_srandom(5831); /* arbitrary */
91   for (int i = 0; i < PSYS_FRAND_COUNT; ++i) {
92     PSYS_FRAND_BASE[i] = BLI_rng_get_float(rng);
93     PSYS_FRAND_SEED_OFFSET[i] = (unsigned int)BLI_rng_get_int(rng);
94     PSYS_FRAND_SEED_MULTIPLIER[i] = (unsigned int)BLI_rng_get_int(rng);
95   }
96   BLI_rng_free(rng);
97 }
98
99 static void get_child_modifier_parameters(ParticleSettings *part,
100                                           ParticleThreadContext *ctx,
101                                           ChildParticle *cpa,
102                                           short cpa_from,
103                                           int cpa_num,
104                                           float *cpa_fuv,
105                                           float *orco,
106                                           ParticleTexture *ptex);
107 static void get_cpa_texture(Mesh *mesh,
108                             ParticleSystem *psys,
109                             ParticleSettings *part,
110                             ParticleData *par,
111                             int child_index,
112                             int face_index,
113                             const float fw[4],
114                             float *orco,
115                             ParticleTexture *ptex,
116                             int event,
117                             float cfra);
118
119 /* few helpers for countall etc. */
120 int count_particles(ParticleSystem *psys)
121 {
122   ParticleSettings *part = psys->part;
123   PARTICLE_P;
124   int tot = 0;
125
126   LOOP_SHOWN_PARTICLES
127   {
128     if (pa->alive == PARS_UNBORN && (part->flag & PART_UNBORN) == 0) {
129     }
130     else if (pa->alive == PARS_DEAD && (part->flag & PART_DIED) == 0) {
131     }
132     else {
133       tot++;
134     }
135   }
136   return tot;
137 }
138 int count_particles_mod(ParticleSystem *psys, int totgr, int cur)
139 {
140   ParticleSettings *part = psys->part;
141   PARTICLE_P;
142   int tot = 0;
143
144   LOOP_SHOWN_PARTICLES
145   {
146     if (pa->alive == PARS_UNBORN && (part->flag & PART_UNBORN) == 0) {
147     }
148     else if (pa->alive == PARS_DEAD && (part->flag & PART_DIED) == 0) {
149     }
150     else if (p % totgr == cur) {
151       tot++;
152     }
153   }
154   return tot;
155 }
156 /* we allocate path cache memory in chunks instead of a big contiguous
157  * chunk, windows' memory allocater fails to find big blocks of memory often */
158
159 #define PATH_CACHE_BUF_SIZE 1024
160
161 static ParticleCacheKey *pcache_key_segment_endpoint_safe(ParticleCacheKey *key)
162 {
163   return (key->segments > 0) ? (key + (key->segments - 1)) : key;
164 }
165
166 static ParticleCacheKey **psys_alloc_path_cache_buffers(ListBase *bufs, int tot, int totkeys)
167 {
168   LinkData *buf;
169   ParticleCacheKey **cache;
170   int i, totkey, totbufkey;
171
172   tot = MAX2(tot, 1);
173   totkey = 0;
174   cache = MEM_callocN(tot * sizeof(void *), "PathCacheArray");
175
176   while (totkey < tot) {
177     totbufkey = MIN2(tot - totkey, PATH_CACHE_BUF_SIZE);
178     buf = MEM_callocN(sizeof(LinkData), "PathCacheLinkData");
179     buf->data = MEM_callocN(sizeof(ParticleCacheKey) * totbufkey * totkeys, "ParticleCacheKey");
180
181     for (i = 0; i < totbufkey; i++) {
182       cache[totkey + i] = ((ParticleCacheKey *)buf->data) + i * totkeys;
183     }
184
185     totkey += totbufkey;
186     BLI_addtail(bufs, buf);
187   }
188
189   return cache;
190 }
191
192 static void psys_free_path_cache_buffers(ParticleCacheKey **cache, ListBase *bufs)
193 {
194   LinkData *buf;
195
196   if (cache) {
197     MEM_freeN(cache);
198   }
199
200   for (buf = bufs->first; buf; buf = buf->next) {
201     MEM_freeN(buf->data);
202   }
203   BLI_freelistN(bufs);
204 }
205
206 /************************************************/
207 /*          Getting stuff                       */
208 /************************************************/
209 /* get object's active particle system safely */
210 ParticleSystem *psys_get_current(Object *ob)
211 {
212   ParticleSystem *psys;
213   if (ob == NULL) {
214     return NULL;
215   }
216
217   for (psys = ob->particlesystem.first; psys; psys = psys->next) {
218     if (psys->flag & PSYS_CURRENT) {
219       return psys;
220     }
221   }
222
223   return NULL;
224 }
225 short psys_get_current_num(Object *ob)
226 {
227   ParticleSystem *psys;
228   short i;
229
230   if (ob == NULL) {
231     return 0;
232   }
233
234   for (psys = ob->particlesystem.first, i = 0; psys; psys = psys->next, i++) {
235     if (psys->flag & PSYS_CURRENT) {
236       return i;
237     }
238   }
239
240   return i;
241 }
242 void psys_set_current_num(Object *ob, int index)
243 {
244   ParticleSystem *psys;
245   short i;
246
247   if (ob == NULL) {
248     return;
249   }
250
251   for (psys = ob->particlesystem.first, i = 0; psys; psys = psys->next, i++) {
252     if (i == index) {
253       psys->flag |= PSYS_CURRENT;
254     }
255     else {
256       psys->flag &= ~PSYS_CURRENT;
257     }
258   }
259 }
260
261 struct LatticeDeformData *psys_create_lattice_deform_data(ParticleSimulationData *sim)
262 {
263   struct LatticeDeformData *lattice_deform_data = NULL;
264
265   if (psys_in_edit_mode(sim->depsgraph, sim->psys) == 0) {
266     Object *lattice = NULL;
267     ModifierData *md = (ModifierData *)psys_get_modifier(sim->ob, sim->psys);
268     bool for_render = DEG_get_mode(sim->depsgraph) == DAG_EVAL_RENDER;
269     int mode = for_render ? eModifierMode_Render : eModifierMode_Realtime;
270
271     for (; md; md = md->next) {
272       if (md->type == eModifierType_Lattice) {
273         if (md->mode & mode) {
274           LatticeModifierData *lmd = (LatticeModifierData *)md;
275           lattice = lmd->object;
276           sim->psys->lattice_strength = lmd->strength;
277         }
278
279         break;
280       }
281     }
282     if (lattice) {
283       lattice_deform_data = init_latt_deform(lattice, NULL);
284     }
285   }
286
287   return lattice_deform_data;
288 }
289 void psys_disable_all(Object *ob)
290 {
291   ParticleSystem *psys = ob->particlesystem.first;
292
293   for (; psys; psys = psys->next) {
294     psys->flag |= PSYS_DISABLED;
295   }
296 }
297 void psys_enable_all(Object *ob)
298 {
299   ParticleSystem *psys = ob->particlesystem.first;
300
301   for (; psys; psys = psys->next) {
302     psys->flag &= ~PSYS_DISABLED;
303   }
304 }
305
306 ParticleSystem *psys_orig_get(ParticleSystem *psys)
307 {
308   if (psys->orig_psys == NULL) {
309     return psys;
310   }
311   return psys->orig_psys;
312 }
313
314 struct ParticleSystem *psys_eval_get(Depsgraph *depsgraph, Object *object, ParticleSystem *psys)
315 {
316   Object *object_eval = DEG_get_evaluated_object(depsgraph, object);
317   if (object_eval == object) {
318     return psys;
319   }
320   ParticleSystem *psys_eval = object_eval->particlesystem.first;
321   while (psys_eval != NULL) {
322     if (psys_eval->orig_psys == psys) {
323       return psys_eval;
324     }
325     psys_eval = psys_eval->next;
326   }
327   return psys_eval;
328 }
329
330 static PTCacheEdit *psys_orig_edit_get(ParticleSystem *psys)
331 {
332   if (psys->orig_psys == NULL) {
333     return psys->edit;
334   }
335   return psys->orig_psys->edit;
336 }
337
338 bool psys_in_edit_mode(Depsgraph *depsgraph, const ParticleSystem *psys)
339 {
340   const ViewLayer *view_layer = DEG_get_input_view_layer(depsgraph);
341   if (view_layer->basact == NULL) {
342     /* TODO(sergey): Needs double-check with multi-object edit. */
343     return false;
344   }
345   const bool use_render_params = (DEG_get_mode(depsgraph) == DAG_EVAL_RENDER);
346   const Object *object = view_layer->basact->object;
347   if (object->mode != OB_MODE_PARTICLE_EDIT) {
348     return false;
349   }
350   const ParticleSystem *psys_orig = psys_orig_get((ParticleSystem *)psys);
351   return (psys_orig->edit || psys->pointcache->edit) && (use_render_params == false);
352 }
353
354 bool psys_check_enabled(Object *ob, ParticleSystem *psys, const bool use_render_params)
355 {
356   ParticleSystemModifierData *psmd;
357
358   if (psys->flag & PSYS_DISABLED || psys->flag & PSYS_DELETE || !psys->part) {
359     return 0;
360   }
361
362   psmd = psys_get_modifier(ob, psys);
363   if (use_render_params) {
364     if (!(psmd->modifier.mode & eModifierMode_Render)) {
365       return 0;
366     }
367   }
368   else if (!(psmd->modifier.mode & eModifierMode_Realtime)) {
369     return 0;
370   }
371
372   return 1;
373 }
374
375 bool psys_check_edited(ParticleSystem *psys)
376 {
377   if (psys->part && psys->part->type == PART_HAIR) {
378     return (psys->flag & PSYS_EDITED || (psys->edit && psys->edit->edited));
379   }
380   else {
381     return (psys->pointcache->edit && psys->pointcache->edit->edited);
382   }
383 }
384
385 void psys_find_group_weights(ParticleSettings *part)
386 {
387   /* Find object pointers based on index. If the collection is linked from
388    * another library linking may not have the object pointers available on
389    * file load, so we have to retrieve them later. See T49273. */
390   const ListBase instance_collection_objects = BKE_collection_object_cache_get(
391       part->instance_collection);
392
393   for (ParticleDupliWeight *dw = part->instance_weights.first; dw; dw = dw->next) {
394     if (dw->ob == NULL) {
395       Base *base = BLI_findlink(&instance_collection_objects, dw->index);
396       if (base != NULL) {
397         dw->ob = base->object;
398       }
399     }
400   }
401 }
402
403 void psys_check_group_weights(ParticleSettings *part)
404 {
405   ParticleDupliWeight *dw, *tdw;
406
407   if (part->ren_as != PART_DRAW_GR || !part->instance_collection) {
408     BLI_freelistN(&part->instance_weights);
409     return;
410   }
411
412   /* Find object pointers. */
413   psys_find_group_weights(part);
414
415   /* Remove NULL objects, that were removed from the collection. */
416   dw = part->instance_weights.first;
417   while (dw) {
418     if (dw->ob == NULL ||
419         !BKE_collection_has_object_recursive(part->instance_collection, dw->ob)) {
420       tdw = dw->next;
421       BLI_freelinkN(&part->instance_weights, dw);
422       dw = tdw;
423     }
424     else {
425       dw = dw->next;
426     }
427   }
428
429   /* Add new objects in the collection. */
430   int index = 0;
431   FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN (part->instance_collection, object) {
432     dw = part->instance_weights.first;
433     while (dw && dw->ob != object) {
434       dw = dw->next;
435     }
436
437     if (!dw) {
438       dw = MEM_callocN(sizeof(ParticleDupliWeight), "ParticleDupliWeight");
439       dw->ob = object;
440       dw->count = 1;
441       BLI_addtail(&part->instance_weights, dw);
442     }
443
444     dw->index = index++;
445   }
446   FOREACH_COLLECTION_OBJECT_RECURSIVE_END;
447
448   /* Ensure there is an element marked as current. */
449   int current = 0;
450   for (dw = part->instance_weights.first; dw; dw = dw->next) {
451     if (dw->flag & PART_DUPLIW_CURRENT) {
452       current = 1;
453       break;
454     }
455   }
456
457   if (!current) {
458     dw = part->instance_weights.first;
459     if (dw) {
460       dw->flag |= PART_DUPLIW_CURRENT;
461     }
462   }
463 }
464
465 int psys_uses_gravity(ParticleSimulationData *sim)
466 {
467   return sim->scene->physics_settings.flag & PHYS_GLOBAL_GRAVITY && sim->psys->part &&
468          sim->psys->part->effector_weights->global_gravity != 0.0f;
469 }
470 /************************************************/
471 /*          Freeing stuff                       */
472 /************************************************/
473 static void fluid_free_settings(SPHFluidSettings *fluid)
474 {
475   if (fluid) {
476     MEM_freeN(fluid);
477   }
478 }
479
480 /** Free (or release) any data used by this particle settings (does not free the partsett itself). */
481 void BKE_particlesettings_free(ParticleSettings *part)
482 {
483   int a;
484
485   BKE_animdata_free((ID *)part, false);
486
487   for (a = 0; a < MAX_MTEX; a++) {
488     MEM_SAFE_FREE(part->mtex[a]);
489   }
490
491   if (part->clumpcurve) {
492     curvemapping_free(part->clumpcurve);
493   }
494   if (part->roughcurve) {
495     curvemapping_free(part->roughcurve);
496   }
497   if (part->twistcurve) {
498     curvemapping_free(part->twistcurve);
499   }
500
501   BKE_partdeflect_free(part->pd);
502   BKE_partdeflect_free(part->pd2);
503
504   MEM_SAFE_FREE(part->effector_weights);
505
506   BLI_freelistN(&part->instance_weights);
507
508   boid_free_settings(part->boids);
509   fluid_free_settings(part->fluid);
510 }
511
512 void free_hair(Object *object, ParticleSystem *psys, int dynamics)
513 {
514   PARTICLE_P;
515
516   LOOP_PARTICLES
517   {
518     if (pa->hair) {
519       MEM_freeN(pa->hair);
520     }
521     pa->hair = NULL;
522     pa->totkey = 0;
523   }
524
525   psys->flag &= ~PSYS_HAIR_DONE;
526
527   if (psys->clmd) {
528     if (dynamics) {
529       modifier_free((ModifierData *)psys->clmd);
530       psys->clmd = NULL;
531       PTCacheID pid;
532       BKE_ptcache_id_from_particles(&pid, object, psys);
533       BKE_ptcache_id_clear(&pid, PTCACHE_CLEAR_ALL, 0);
534     }
535     else {
536       cloth_free_modifier(psys->clmd);
537     }
538   }
539
540   if (psys->hair_in_mesh) {
541     BKE_id_free(NULL, psys->hair_in_mesh);
542   }
543   psys->hair_in_mesh = NULL;
544
545   if (psys->hair_out_mesh) {
546     BKE_id_free(NULL, psys->hair_out_mesh);
547   }
548   psys->hair_out_mesh = NULL;
549 }
550 void free_keyed_keys(ParticleSystem *psys)
551 {
552   PARTICLE_P;
553
554   if (psys->part->type == PART_HAIR) {
555     return;
556   }
557
558   if (psys->particles && psys->particles->keys) {
559     MEM_freeN(psys->particles->keys);
560
561     LOOP_PARTICLES
562     {
563       if (pa->keys) {
564         pa->keys = NULL;
565         pa->totkey = 0;
566       }
567     }
568   }
569 }
570 static void free_child_path_cache(ParticleSystem *psys)
571 {
572   psys_free_path_cache_buffers(psys->childcache, &psys->childcachebufs);
573   psys->childcache = NULL;
574   psys->totchildcache = 0;
575 }
576 void psys_free_path_cache(ParticleSystem *psys, PTCacheEdit *edit)
577 {
578   if (edit) {
579     psys_free_path_cache_buffers(edit->pathcache, &edit->pathcachebufs);
580     edit->pathcache = NULL;
581     edit->totcached = 0;
582   }
583   if (psys) {
584     psys_free_path_cache_buffers(psys->pathcache, &psys->pathcachebufs);
585     psys->pathcache = NULL;
586     psys->totcached = 0;
587
588     free_child_path_cache(psys);
589   }
590 }
591 void psys_free_children(ParticleSystem *psys)
592 {
593   if (psys->child) {
594     MEM_freeN(psys->child);
595     psys->child = NULL;
596     psys->totchild = 0;
597   }
598
599   free_child_path_cache(psys);
600 }
601 void psys_free_particles(ParticleSystem *psys)
602 {
603   PARTICLE_P;
604
605   if (psys->particles) {
606     /* Even though psys->part should never be NULL, this can happen as an exception during deletion.
607      * See ID_REMAP_SKIP/FORCE/FLAG_NEVER_NULL_USAGE in BKE_library_remap. */
608     if (psys->part && psys->part->type == PART_HAIR) {
609       LOOP_PARTICLES
610       {
611         if (pa->hair) {
612           MEM_freeN(pa->hair);
613         }
614       }
615     }
616
617     if (psys->particles->keys) {
618       MEM_freeN(psys->particles->keys);
619     }
620
621     if (psys->particles->boid) {
622       MEM_freeN(psys->particles->boid);
623     }
624
625     MEM_freeN(psys->particles);
626     psys->particles = NULL;
627     psys->totpart = 0;
628   }
629 }
630 void psys_free_pdd(ParticleSystem *psys)
631 {
632   if (psys->pdd) {
633     if (psys->pdd->cdata) {
634       MEM_freeN(psys->pdd->cdata);
635     }
636     psys->pdd->cdata = NULL;
637
638     if (psys->pdd->vdata) {
639       MEM_freeN(psys->pdd->vdata);
640     }
641     psys->pdd->vdata = NULL;
642
643     if (psys->pdd->ndata) {
644       MEM_freeN(psys->pdd->ndata);
645     }
646     psys->pdd->ndata = NULL;
647
648     if (psys->pdd->vedata) {
649       MEM_freeN(psys->pdd->vedata);
650     }
651     psys->pdd->vedata = NULL;
652
653     psys->pdd->totpoint = 0;
654     psys->pdd->totpart = 0;
655     psys->pdd->partsize = 0;
656   }
657 }
658 /* free everything */
659 void psys_free(Object *ob, ParticleSystem *psys)
660 {
661   if (psys) {
662     int nr = 0;
663     ParticleSystem *tpsys;
664
665     psys_free_path_cache(psys, NULL);
666
667     /* NOTE: We pass dynamics=0 to free_hair() to prevent it from doing an
668      * unneeded clear of the cache. But for historical reason that code path
669      * was only clearing cloth part of modifier data.
670      *
671      * Part of the story there is that particle evaluation is trying to not
672      * re-allocate thew ModifierData itself, and limits all allocations to
673      * the cloth part of it.
674      *
675      * Why evaluation is relying on hair_free() and in some specific code
676      * paths there is beyond me.
677      */
678     free_hair(ob, psys, 0);
679     if (psys->clmd != NULL) {
680       modifier_free((ModifierData *)psys->clmd);
681     }
682
683     psys_free_particles(psys);
684
685     if (psys->edit && psys->free_edit) {
686       psys->free_edit(psys->edit);
687     }
688
689     if (psys->child) {
690       MEM_freeN(psys->child);
691       psys->child = NULL;
692       psys->totchild = 0;
693     }
694
695     /* check if we are last non-visible particle system */
696     for (tpsys = ob->particlesystem.first; tpsys; tpsys = tpsys->next) {
697       if (tpsys->part) {
698         if (ELEM(tpsys->part->ren_as, PART_DRAW_OB, PART_DRAW_GR)) {
699           nr++;
700           break;
701         }
702       }
703     }
704     /* clear do-not-draw-flag */
705     if (!nr) {
706       ob->transflag &= ~OB_DUPLIPARTS;
707     }
708
709     psys->part = NULL;
710
711     if ((psys->flag & PSYS_SHARED_CACHES) == 0) {
712       BKE_ptcache_free_list(&psys->ptcaches);
713     }
714     psys->pointcache = NULL;
715
716     BLI_freelistN(&psys->targets);
717
718     BLI_bvhtree_free(psys->bvhtree);
719     BLI_kdtree_3d_free(psys->tree);
720
721     if (psys->fluid_springs) {
722       MEM_freeN(psys->fluid_springs);
723     }
724
725     BKE_effectors_free(psys->effectors);
726
727     if (psys->pdd) {
728       psys_free_pdd(psys);
729       MEM_freeN(psys->pdd);
730     }
731
732     BKE_particle_batch_cache_free(psys);
733
734     MEM_freeN(psys);
735   }
736 }
737
738 void psys_copy_particles(ParticleSystem *psys_dst, ParticleSystem *psys_src)
739 {
740   /* Free existing particles. */
741   if (psys_dst->particles != psys_src->particles) {
742     psys_free_particles(psys_dst);
743   }
744   if (psys_dst->child != psys_src->child) {
745     psys_free_children(psys_dst);
746   }
747   /* Restore counters. */
748   psys_dst->totpart = psys_src->totpart;
749   psys_dst->totchild = psys_src->totchild;
750   /* Copy particles and children. */
751   psys_dst->particles = MEM_dupallocN(psys_src->particles);
752   psys_dst->child = MEM_dupallocN(psys_src->child);
753   if (psys_dst->part->type == PART_HAIR) {
754     ParticleData *pa;
755     int p;
756     for (p = 0, pa = psys_dst->particles; p < psys_dst->totpart; p++, pa++) {
757       pa->hair = MEM_dupallocN(pa->hair);
758     }
759   }
760   if (psys_dst->particles && (psys_dst->particles->keys || psys_dst->particles->boid)) {
761     ParticleKey *key = psys_dst->particles->keys;
762     BoidParticle *boid = psys_dst->particles->boid;
763     ParticleData *pa;
764     int p;
765     if (key != NULL) {
766       key = MEM_dupallocN(key);
767     }
768     if (boid != NULL) {
769       boid = MEM_dupallocN(boid);
770     }
771     for (p = 0, pa = psys_dst->particles; p < psys_dst->totpart; p++, pa++) {
772       if (boid != NULL) {
773         pa->boid = boid++;
774       }
775       if (key != NULL) {
776         pa->keys = key;
777         key += pa->totkey;
778       }
779     }
780   }
781 }
782
783 /************************************************/
784 /*          Interpolation                       */
785 /************************************************/
786 static float interpolate_particle_value(
787     float v1, float v2, float v3, float v4, const float w[4], int four)
788 {
789   float value;
790
791   value = w[0] * v1 + w[1] * v2 + w[2] * v3;
792   if (four) {
793     value += w[3] * v4;
794   }
795
796   CLAMP(value, 0.f, 1.f);
797
798   return value;
799 }
800
801 void psys_interpolate_particle(
802     short type, ParticleKey keys[4], float dt, ParticleKey *result, bool velocity)
803 {
804   float t[4];
805
806   if (type < 0) {
807     interp_cubic_v3(result->co, result->vel, keys[1].co, keys[1].vel, keys[2].co, keys[2].vel, dt);
808   }
809   else {
810     key_curve_position_weights(dt, t, type);
811
812     interp_v3_v3v3v3v3(result->co, keys[0].co, keys[1].co, keys[2].co, keys[3].co, t);
813
814     if (velocity) {
815       float temp[3];
816
817       if (dt > 0.999f) {
818         key_curve_position_weights(dt - 0.001f, t, type);
819         interp_v3_v3v3v3v3(temp, keys[0].co, keys[1].co, keys[2].co, keys[3].co, t);
820         sub_v3_v3v3(result->vel, result->co, temp);
821       }
822       else {
823         key_curve_position_weights(dt + 0.001f, t, type);
824         interp_v3_v3v3v3v3(temp, keys[0].co, keys[1].co, keys[2].co, keys[3].co, t);
825         sub_v3_v3v3(result->vel, temp, result->co);
826       }
827     }
828   }
829 }
830
831 typedef struct ParticleInterpolationData {
832   HairKey *hkey[2];
833
834   Mesh *mesh;
835   MVert *mvert[2];
836
837   int keyed;
838   ParticleKey *kkey[2];
839
840   PointCache *cache;
841   PTCacheMem *pm;
842
843   PTCacheEditPoint *epoint;
844   PTCacheEditKey *ekey[2];
845
846   float birthtime, dietime;
847   int bspline;
848 } ParticleInterpolationData;
849 /* Assumes pointcache->mem_cache exists, so for disk cached particles call psys_make_temp_pointcache() before use */
850 /* It uses ParticleInterpolationData->pm to store the current memory cache frame so it's thread safe. */
851 static void get_pointcache_keys_for_time(Object *UNUSED(ob),
852                                          PointCache *cache,
853                                          PTCacheMem **cur,
854                                          int index,
855                                          float t,
856                                          ParticleKey *key1,
857                                          ParticleKey *key2)
858 {
859   static PTCacheMem *pm = NULL;
860   int index1, index2;
861
862   if (index < 0) { /* initialize */
863     *cur = cache->mem_cache.first;
864
865     if (*cur) {
866       *cur = (*cur)->next;
867     }
868   }
869   else {
870     if (*cur) {
871       while (*cur && (*cur)->next && (float)(*cur)->frame < t) {
872         *cur = (*cur)->next;
873       }
874
875       pm = *cur;
876
877       index2 = BKE_ptcache_mem_index_find(pm, index);
878       index1 = BKE_ptcache_mem_index_find(pm->prev, index);
879       if (index2 < 0) {
880         return;
881       }
882
883       BKE_ptcache_make_particle_key(key2, index2, pm->data, (float)pm->frame);
884       if (index1 < 0) {
885         copy_particle_key(key1, key2, 1);
886       }
887       else {
888         BKE_ptcache_make_particle_key(key1, index1, pm->prev->data, (float)pm->prev->frame);
889       }
890     }
891     else if (cache->mem_cache.first) {
892       pm = cache->mem_cache.first;
893       index2 = BKE_ptcache_mem_index_find(pm, index);
894       if (index2 < 0) {
895         return;
896       }
897       BKE_ptcache_make_particle_key(key2, index2, pm->data, (float)pm->frame);
898       copy_particle_key(key1, key2, 1);
899     }
900   }
901 }
902 static int get_pointcache_times_for_particle(PointCache *cache,
903                                              int index,
904                                              float *start,
905                                              float *end)
906 {
907   PTCacheMem *pm;
908   int ret = 0;
909
910   for (pm = cache->mem_cache.first; pm; pm = pm->next) {
911     if (BKE_ptcache_mem_index_find(pm, index) >= 0) {
912       *start = pm->frame;
913       ret++;
914       break;
915     }
916   }
917
918   for (pm = cache->mem_cache.last; pm; pm = pm->prev) {
919     if (BKE_ptcache_mem_index_find(pm, index) >= 0) {
920       *end = pm->frame;
921       ret++;
922       break;
923     }
924   }
925
926   return ret == 2;
927 }
928
929 float psys_get_dietime_from_cache(PointCache *cache, int index)
930 {
931   PTCacheMem *pm;
932   int dietime = 10000000; /* some max value so that we can default to pa->time+lifetime */
933
934   for (pm = cache->mem_cache.last; pm; pm = pm->prev) {
935     if (BKE_ptcache_mem_index_find(pm, index) >= 0) {
936       return (float)pm->frame;
937     }
938   }
939
940   return (float)dietime;
941 }
942
943 static void init_particle_interpolation(Object *ob,
944                                         ParticleSystem *psys,
945                                         ParticleData *pa,
946                                         ParticleInterpolationData *pind)
947 {
948
949   if (pind->epoint) {
950     PTCacheEditPoint *point = pind->epoint;
951
952     pind->ekey[0] = point->keys;
953     pind->ekey[1] = point->totkey > 1 ? point->keys + 1 : NULL;
954
955     pind->birthtime = *(point->keys->time);
956     pind->dietime = *((point->keys + point->totkey - 1)->time);
957   }
958   else if (pind->keyed) {
959     ParticleKey *key = pa->keys;
960     pind->kkey[0] = key;
961     pind->kkey[1] = pa->totkey > 1 ? key + 1 : NULL;
962
963     pind->birthtime = key->time;
964     pind->dietime = (key + pa->totkey - 1)->time;
965   }
966   else if (pind->cache) {
967     float start = 0.0f, end = 0.0f;
968     get_pointcache_keys_for_time(ob, pind->cache, &pind->pm, -1, 0.0f, NULL, NULL);
969     pind->birthtime = pa ? pa->time : pind->cache->startframe;
970     pind->dietime = pa ? pa->dietime : pind->cache->endframe;
971
972     if (get_pointcache_times_for_particle(pind->cache, pa - psys->particles, &start, &end)) {
973       pind->birthtime = MAX2(pind->birthtime, start);
974       pind->dietime = MIN2(pind->dietime, end);
975     }
976   }
977   else {
978     HairKey *key = pa->hair;
979     pind->hkey[0] = key;
980     pind->hkey[1] = key + 1;
981
982     pind->birthtime = key->time;
983     pind->dietime = (key + pa->totkey - 1)->time;
984
985     if (pind->mesh) {
986       pind->mvert[0] = &pind->mesh->mvert[pa->hair_index];
987       pind->mvert[1] = pind->mvert[0] + 1;
988     }
989   }
990 }
991 static void edit_to_particle(ParticleKey *key, PTCacheEditKey *ekey)
992 {
993   copy_v3_v3(key->co, ekey->co);
994   if (ekey->vel) {
995     copy_v3_v3(key->vel, ekey->vel);
996   }
997   key->time = *(ekey->time);
998 }
999 static void hair_to_particle(ParticleKey *key, HairKey *hkey)
1000 {
1001   copy_v3_v3(key->co, hkey->co);
1002   key->time = hkey->time;
1003 }
1004
1005 static void mvert_to_particle(ParticleKey *key, MVert *mvert, HairKey *hkey)
1006 {
1007   copy_v3_v3(key->co, mvert->co);
1008   key->time = hkey->time;
1009 }
1010
1011 static void do_particle_interpolation(ParticleSystem *psys,
1012                                       int p,
1013                                       ParticleData *pa,
1014                                       float t,
1015                                       ParticleInterpolationData *pind,
1016                                       ParticleKey *result)
1017 {
1018   PTCacheEditPoint *point = pind->epoint;
1019   ParticleKey keys[4];
1020   int point_vel = (point && point->keys->vel);
1021   float real_t, dfra, keytime, invdt = 1.f;
1022
1023   /* billboards wont fill in all of these, so start cleared */
1024   memset(keys, 0, sizeof(keys));
1025
1026   /* interpret timing and find keys */
1027   if (point) {
1028     if (result->time < 0.0f) {
1029       real_t = -result->time;
1030     }
1031     else {
1032       real_t = *(pind->ekey[0]->time) +
1033                t * (*(pind->ekey[0][point->totkey - 1].time) - *(pind->ekey[0]->time));
1034     }
1035
1036     while (*(pind->ekey[1]->time) < real_t) {
1037       pind->ekey[1]++;
1038     }
1039
1040     pind->ekey[0] = pind->ekey[1] - 1;
1041   }
1042   else if (pind->keyed) {
1043     /* we have only one key, so let's use that */
1044     if (pind->kkey[1] == NULL) {
1045       copy_particle_key(result, pind->kkey[0], 1);
1046       return;
1047     }
1048
1049     if (result->time < 0.0f) {
1050       real_t = -result->time;
1051     }
1052     else {
1053       real_t = pind->kkey[0]->time +
1054                t * (pind->kkey[0][pa->totkey - 1].time - pind->kkey[0]->time);
1055     }
1056
1057     if (psys->part->phystype == PART_PHYS_KEYED && psys->flag & PSYS_KEYED_TIMING) {
1058       ParticleTarget *pt = psys->targets.first;
1059
1060       pt = pt->next;
1061
1062       while (pt && pa->time + pt->time < real_t) {
1063         pt = pt->next;
1064       }
1065
1066       if (pt) {
1067         pt = pt->prev;
1068
1069         if (pa->time + pt->time + pt->duration > real_t) {
1070           real_t = pa->time + pt->time;
1071         }
1072       }
1073       else {
1074         real_t = pa->time + ((ParticleTarget *)psys->targets.last)->time;
1075       }
1076     }
1077
1078     CLAMP(real_t, pa->time, pa->dietime);
1079
1080     while (pind->kkey[1]->time < real_t) {
1081       pind->kkey[1]++;
1082     }
1083
1084     pind->kkey[0] = pind->kkey[1] - 1;
1085   }
1086   else if (pind->cache) {
1087     if (result->time < 0.0f) { /* flag for time in frames */
1088       real_t = -result->time;
1089     }
1090     else {
1091       real_t = pa->time + t * (pa->dietime - pa->time);
1092     }
1093   }
1094   else {
1095     if (result->time < 0.0f) {
1096       real_t = -result->time;
1097     }
1098     else {
1099       real_t = pind->hkey[0]->time +
1100                t * (pind->hkey[0][pa->totkey - 1].time - pind->hkey[0]->time);
1101     }
1102
1103     while (pind->hkey[1]->time < real_t) {
1104       pind->hkey[1]++;
1105       pind->mvert[1]++;
1106     }
1107
1108     pind->hkey[0] = pind->hkey[1] - 1;
1109   }
1110
1111   /* set actual interpolation keys */
1112   if (point) {
1113     edit_to_particle(keys + 1, pind->ekey[0]);
1114     edit_to_particle(keys + 2, pind->ekey[1]);
1115   }
1116   else if (pind->mesh) {
1117     pind->mvert[0] = pind->mvert[1] - 1;
1118     mvert_to_particle(keys + 1, pind->mvert[0], pind->hkey[0]);
1119     mvert_to_particle(keys + 2, pind->mvert[1], pind->hkey[1]);
1120   }
1121   else if (pind->keyed) {
1122     memcpy(keys + 1, pind->kkey[0], sizeof(ParticleKey));
1123     memcpy(keys + 2, pind->kkey[1], sizeof(ParticleKey));
1124   }
1125   else if (pind->cache) {
1126     get_pointcache_keys_for_time(NULL, pind->cache, &pind->pm, p, real_t, keys + 1, keys + 2);
1127   }
1128   else {
1129     hair_to_particle(keys + 1, pind->hkey[0]);
1130     hair_to_particle(keys + 2, pind->hkey[1]);
1131   }
1132
1133   /* set secondary interpolation keys for hair */
1134   if (!pind->keyed && !pind->cache && !point_vel) {
1135     if (point) {
1136       if (pind->ekey[0] != point->keys) {
1137         edit_to_particle(keys, pind->ekey[0] - 1);
1138       }
1139       else {
1140         edit_to_particle(keys, pind->ekey[0]);
1141       }
1142     }
1143     else if (pind->mesh) {
1144       if (pind->hkey[0] != pa->hair) {
1145         mvert_to_particle(keys, pind->mvert[0] - 1, pind->hkey[0] - 1);
1146       }
1147       else {
1148         mvert_to_particle(keys, pind->mvert[0], pind->hkey[0]);
1149       }
1150     }
1151     else {
1152       if (pind->hkey[0] != pa->hair) {
1153         hair_to_particle(keys, pind->hkey[0] - 1);
1154       }
1155       else {
1156         hair_to_particle(keys, pind->hkey[0]);
1157       }
1158     }
1159
1160     if (point) {
1161       if (pind->ekey[1] != point->keys + point->totkey - 1) {
1162         edit_to_particle(keys + 3, pind->ekey[1] + 1);
1163       }
1164       else {
1165         edit_to_particle(keys + 3, pind->ekey[1]);
1166       }
1167     }
1168     else if (pind->mesh) {
1169       if (pind->hkey[1] != pa->hair + pa->totkey - 1) {
1170         mvert_to_particle(keys + 3, pind->mvert[1] + 1, pind->hkey[1] + 1);
1171       }
1172       else {
1173         mvert_to_particle(keys + 3, pind->mvert[1], pind->hkey[1]);
1174       }
1175     }
1176     else {
1177       if (pind->hkey[1] != pa->hair + pa->totkey - 1) {
1178         hair_to_particle(keys + 3, pind->hkey[1] + 1);
1179       }
1180       else {
1181         hair_to_particle(keys + 3, pind->hkey[1]);
1182       }
1183     }
1184   }
1185
1186   dfra = keys[2].time - keys[1].time;
1187   keytime = (real_t - keys[1].time) / dfra;
1188
1189   /* convert velocity to timestep size */
1190   if (pind->keyed || pind->cache || point_vel) {
1191     invdt = dfra * 0.04f * (psys ? psys->part->timetweak : 1.f);
1192     mul_v3_fl(keys[1].vel, invdt);
1193     mul_v3_fl(keys[2].vel, invdt);
1194     interp_qt_qtqt(result->rot, keys[1].rot, keys[2].rot, keytime);
1195   }
1196
1197   /* now we should have in chronologiacl order k1<=k2<=t<=k3<=k4 with keytime between [0, 1]->[k2, k3] (k1 & k4 used for cardinal & bspline interpolation)*/
1198   psys_interpolate_particle((pind->keyed || pind->cache || point_vel) ?
1199                                 -1 /* signal for cubic interpolation */
1200                                 :
1201                                 (pind->bspline ? KEY_BSPLINE : KEY_CARDINAL),
1202                             keys,
1203                             keytime,
1204                             result,
1205                             1);
1206
1207   /* the velocity needs to be converted back from cubic interpolation */
1208   if (pind->keyed || pind->cache || point_vel) {
1209     mul_v3_fl(result->vel, 1.f / invdt);
1210   }
1211 }
1212
1213 static void interpolate_pathcache(ParticleCacheKey *first, float t, ParticleCacheKey *result)
1214 {
1215   int i = 0;
1216   ParticleCacheKey *cur = first;
1217
1218   /* scale the requested time to fit the entire path even if the path is cut early */
1219   t *= (first + first->segments)->time;
1220
1221   while (i < first->segments && cur->time < t) {
1222     cur++;
1223   }
1224
1225   if (cur->time == t) {
1226     *result = *cur;
1227   }
1228   else {
1229     float dt = (t - (cur - 1)->time) / (cur->time - (cur - 1)->time);
1230     interp_v3_v3v3(result->co, (cur - 1)->co, cur->co, dt);
1231     interp_v3_v3v3(result->vel, (cur - 1)->vel, cur->vel, dt);
1232     interp_qt_qtqt(result->rot, (cur - 1)->rot, cur->rot, dt);
1233     result->time = t;
1234   }
1235
1236   /* first is actual base rotation, others are incremental from first */
1237   if (cur == first || cur - 1 == first) {
1238     copy_qt_qt(result->rot, first->rot);
1239   }
1240   else {
1241     mul_qt_qtqt(result->rot, first->rot, result->rot);
1242   }
1243 }
1244
1245 /************************************************/
1246 /*          Particles on a dm                   */
1247 /************************************************/
1248 /* interpolate a location on a face based on face coordinates */
1249 void psys_interpolate_face(MVert *mvert,
1250                            MFace *mface,
1251                            MTFace *tface,
1252                            float (*orcodata)[3],
1253                            float w[4],
1254                            float vec[3],
1255                            float nor[3],
1256                            float utan[3],
1257                            float vtan[3],
1258                            float orco[3])
1259 {
1260   float *v1 = 0, *v2 = 0, *v3 = 0, *v4 = 0;
1261   float e1[3], e2[3], s1, s2, t1, t2;
1262   float *uv1, *uv2, *uv3, *uv4;
1263   float n1[3], n2[3], n3[3], n4[3];
1264   float tuv[4][2];
1265   float *o1, *o2, *o3, *o4;
1266
1267   v1 = mvert[mface->v1].co;
1268   v2 = mvert[mface->v2].co;
1269   v3 = mvert[mface->v3].co;
1270
1271   normal_short_to_float_v3(n1, mvert[mface->v1].no);
1272   normal_short_to_float_v3(n2, mvert[mface->v2].no);
1273   normal_short_to_float_v3(n3, mvert[mface->v3].no);
1274
1275   if (mface->v4) {
1276     v4 = mvert[mface->v4].co;
1277     normal_short_to_float_v3(n4, mvert[mface->v4].no);
1278
1279     interp_v3_v3v3v3v3(vec, v1, v2, v3, v4, w);
1280
1281     if (nor) {
1282       if (mface->flag & ME_SMOOTH) {
1283         interp_v3_v3v3v3v3(nor, n1, n2, n3, n4, w);
1284       }
1285       else {
1286         normal_quad_v3(nor, v1, v2, v3, v4);
1287       }
1288     }
1289   }
1290   else {
1291     interp_v3_v3v3v3(vec, v1, v2, v3, w);
1292
1293     if (nor) {
1294       if (mface->flag & ME_SMOOTH) {
1295         interp_v3_v3v3v3(nor, n1, n2, n3, w);
1296       }
1297       else {
1298         normal_tri_v3(nor, v1, v2, v3);
1299       }
1300     }
1301   }
1302
1303   /* calculate tangent vectors */
1304   if (utan && vtan) {
1305     if (tface) {
1306       uv1 = tface->uv[0];
1307       uv2 = tface->uv[1];
1308       uv3 = tface->uv[2];
1309       uv4 = tface->uv[3];
1310     }
1311     else {
1312       uv1 = tuv[0];
1313       uv2 = tuv[1];
1314       uv3 = tuv[2];
1315       uv4 = tuv[3];
1316       map_to_sphere(uv1, uv1 + 1, v1[0], v1[1], v1[2]);
1317       map_to_sphere(uv2, uv2 + 1, v2[0], v2[1], v2[2]);
1318       map_to_sphere(uv3, uv3 + 1, v3[0], v3[1], v3[2]);
1319       if (v4) {
1320         map_to_sphere(uv4, uv4 + 1, v4[0], v4[1], v4[2]);
1321       }
1322     }
1323
1324     if (v4) {
1325       s1 = uv3[0] - uv1[0];
1326       s2 = uv4[0] - uv1[0];
1327
1328       t1 = uv3[1] - uv1[1];
1329       t2 = uv4[1] - uv1[1];
1330
1331       sub_v3_v3v3(e1, v3, v1);
1332       sub_v3_v3v3(e2, v4, v1);
1333     }
1334     else {
1335       s1 = uv2[0] - uv1[0];
1336       s2 = uv3[0] - uv1[0];
1337
1338       t1 = uv2[1] - uv1[1];
1339       t2 = uv3[1] - uv1[1];
1340
1341       sub_v3_v3v3(e1, v2, v1);
1342       sub_v3_v3v3(e2, v3, v1);
1343     }
1344
1345     vtan[0] = (s1 * e2[0] - s2 * e1[0]);
1346     vtan[1] = (s1 * e2[1] - s2 * e1[1]);
1347     vtan[2] = (s1 * e2[2] - s2 * e1[2]);
1348
1349     utan[0] = (t1 * e2[0] - t2 * e1[0]);
1350     utan[1] = (t1 * e2[1] - t2 * e1[1]);
1351     utan[2] = (t1 * e2[2] - t2 * e1[2]);
1352   }
1353
1354   if (orco) {
1355     if (orcodata) {
1356       o1 = orcodata[mface->v1];
1357       o2 = orcodata[mface->v2];
1358       o3 = orcodata[mface->v3];
1359
1360       if (mface->v4) {
1361         o4 = orcodata[mface->v4];
1362
1363         interp_v3_v3v3v3v3(orco, o1, o2, o3, o4, w);
1364       }
1365       else {
1366         interp_v3_v3v3v3(orco, o1, o2, o3, w);
1367       }
1368     }
1369     else {
1370       copy_v3_v3(orco, vec);
1371     }
1372   }
1373 }
1374 void psys_interpolate_uvs(const MTFace *tface, int quad, const float w[4], float uvco[2])
1375 {
1376   float v10 = tface->uv[0][0];
1377   float v11 = tface->uv[0][1];
1378   float v20 = tface->uv[1][0];
1379   float v21 = tface->uv[1][1];
1380   float v30 = tface->uv[2][0];
1381   float v31 = tface->uv[2][1];
1382   float v40, v41;
1383
1384   if (quad) {
1385     v40 = tface->uv[3][0];
1386     v41 = tface->uv[3][1];
1387
1388     uvco[0] = w[0] * v10 + w[1] * v20 + w[2] * v30 + w[3] * v40;
1389     uvco[1] = w[0] * v11 + w[1] * v21 + w[2] * v31 + w[3] * v41;
1390   }
1391   else {
1392     uvco[0] = w[0] * v10 + w[1] * v20 + w[2] * v30;
1393     uvco[1] = w[0] * v11 + w[1] * v21 + w[2] * v31;
1394   }
1395 }
1396
1397 void psys_interpolate_mcol(const MCol *mcol, int quad, const float w[4], MCol *mc)
1398 {
1399   const char *cp1, *cp2, *cp3, *cp4;
1400   char *cp;
1401
1402   cp = (char *)mc;
1403   cp1 = (const char *)&mcol[0];
1404   cp2 = (const char *)&mcol[1];
1405   cp3 = (const char *)&mcol[2];
1406
1407   if (quad) {
1408     cp4 = (char *)&mcol[3];
1409
1410     cp[0] = (int)(w[0] * cp1[0] + w[1] * cp2[0] + w[2] * cp3[0] + w[3] * cp4[0]);
1411     cp[1] = (int)(w[0] * cp1[1] + w[1] * cp2[1] + w[2] * cp3[1] + w[3] * cp4[1]);
1412     cp[2] = (int)(w[0] * cp1[2] + w[1] * cp2[2] + w[2] * cp3[2] + w[3] * cp4[2]);
1413     cp[3] = (int)(w[0] * cp1[3] + w[1] * cp2[3] + w[2] * cp3[3] + w[3] * cp4[3]);
1414   }
1415   else {
1416     cp[0] = (int)(w[0] * cp1[0] + w[1] * cp2[0] + w[2] * cp3[0]);
1417     cp[1] = (int)(w[0] * cp1[1] + w[1] * cp2[1] + w[2] * cp3[1]);
1418     cp[2] = (int)(w[0] * cp1[2] + w[1] * cp2[2] + w[2] * cp3[2]);
1419     cp[3] = (int)(w[0] * cp1[3] + w[1] * cp2[3] + w[2] * cp3[3]);
1420   }
1421 }
1422
1423 static float psys_interpolate_value_from_verts(
1424     Mesh *mesh, short from, int index, const float fw[4], const float *values)
1425 {
1426   if (values == 0 || index == -1) {
1427     return 0.0;
1428   }
1429
1430   switch (from) {
1431     case PART_FROM_VERT:
1432       return values[index];
1433     case PART_FROM_FACE:
1434     case PART_FROM_VOLUME: {
1435       MFace *mf = &mesh->mface[index];
1436       return interpolate_particle_value(
1437           values[mf->v1], values[mf->v2], values[mf->v3], values[mf->v4], fw, mf->v4);
1438     }
1439   }
1440   return 0.0f;
1441 }
1442
1443 /* conversion of pa->fw to origspace layer coordinates */
1444 static void psys_w_to_origspace(const float w[4], float uv[2])
1445 {
1446   uv[0] = w[1] + w[2];
1447   uv[1] = w[2] + w[3];
1448 }
1449
1450 /* conversion of pa->fw to weights in face from origspace */
1451 static void psys_origspace_to_w(OrigSpaceFace *osface, int quad, const float w[4], float neww[4])
1452 {
1453   float v[4][3], co[3];
1454
1455   v[0][0] = osface->uv[0][0];
1456   v[0][1] = osface->uv[0][1];
1457   v[0][2] = 0.0f;
1458   v[1][0] = osface->uv[1][0];
1459   v[1][1] = osface->uv[1][1];
1460   v[1][2] = 0.0f;
1461   v[2][0] = osface->uv[2][0];
1462   v[2][1] = osface->uv[2][1];
1463   v[2][2] = 0.0f;
1464
1465   psys_w_to_origspace(w, co);
1466   co[2] = 0.0f;
1467
1468   if (quad) {
1469     v[3][0] = osface->uv[3][0];
1470     v[3][1] = osface->uv[3][1];
1471     v[3][2] = 0.0f;
1472     interp_weights_poly_v3(neww, v, 4, co);
1473   }
1474   else {
1475     interp_weights_poly_v3(neww, v, 3, co);
1476     neww[3] = 0.0f;
1477   }
1478 }
1479
1480 /**
1481  * Find the final derived mesh tessface for a particle, from its original tessface index.
1482  * This is slow and can be optimized but only for many lookups.
1483  *
1484  * \param mesh_final: Final mesh, it may not have the same topology as original mesh.
1485  * \param mesh_original: Original mesh, use for accessing #MPoly to #MFace mapping.
1486  * \param findex_orig: The input tessface index.
1487  * \param fw: Face weights (position of the particle inside the \a findex_orig tessface).
1488  * \param poly_nodes: May be NULL, otherwise an array of linked list,
1489  * one for each final \a mesh_final polygon, containing all its tessfaces indices.
1490  * \return The \a mesh_final tessface index.
1491  */
1492 int psys_particle_dm_face_lookup(Mesh *mesh_final,
1493                                  Mesh *mesh_original,
1494                                  int findex_orig,
1495                                  const float fw[4],
1496                                  struct LinkNode **poly_nodes)
1497 {
1498   MFace *mtessface_final;
1499   OrigSpaceFace *osface_final;
1500   int pindex_orig;
1501   float uv[2], (*faceuv)[2];
1502
1503   const int *index_mf_to_mpoly_deformed = NULL;
1504   const int *index_mf_to_mpoly = NULL;
1505   const int *index_mp_to_orig = NULL;
1506
1507   const int totface_final = mesh_final->totface;
1508   const int totface_deformed = mesh_original ? mesh_original->totface : totface_final;
1509
1510   if (ELEM(0, totface_final, totface_deformed)) {
1511     return DMCACHE_NOTFOUND;
1512   }
1513
1514   index_mf_to_mpoly = CustomData_get_layer(&mesh_final->fdata, CD_ORIGINDEX);
1515   index_mp_to_orig = CustomData_get_layer(&mesh_final->pdata, CD_ORIGINDEX);
1516   BLI_assert(index_mf_to_mpoly);
1517
1518   if (mesh_original) {
1519     index_mf_to_mpoly_deformed = CustomData_get_layer(&mesh_original->fdata, CD_ORIGINDEX);
1520   }
1521   else {
1522     BLI_assert(mesh_final->runtime.deformed_only);
1523     index_mf_to_mpoly_deformed = index_mf_to_mpoly;
1524   }
1525   BLI_assert(index_mf_to_mpoly_deformed);
1526
1527   pindex_orig = index_mf_to_mpoly_deformed[findex_orig];
1528
1529   if (mesh_original == NULL) {
1530     mesh_original = mesh_final;
1531   }
1532
1533   index_mf_to_mpoly_deformed = NULL;
1534
1535   mtessface_final = mesh_final->mface;
1536   osface_final = CustomData_get_layer(&mesh_final->fdata, CD_ORIGSPACE);
1537
1538   if (osface_final == NULL) {
1539     /* Assume we don't need osface_final data, and we get a direct 1-1 mapping... */
1540     if (findex_orig < totface_final) {
1541       //printf("\tNO CD_ORIGSPACE, assuming not needed\n");
1542       return findex_orig;
1543     }
1544     else {
1545       printf("\tNO CD_ORIGSPACE, error out of range\n");
1546       return DMCACHE_NOTFOUND;
1547     }
1548   }
1549   else if (findex_orig >= mesh_original->totface) {
1550     return DMCACHE_NOTFOUND; /* index not in the original mesh */
1551   }
1552
1553   psys_w_to_origspace(fw, uv);
1554
1555   if (poly_nodes) {
1556     /* we can have a restricted linked list of faces to check, faster! */
1557     LinkNode *tessface_node = poly_nodes[pindex_orig];
1558
1559     for (; tessface_node; tessface_node = tessface_node->next) {
1560       int findex_dst = POINTER_AS_INT(tessface_node->link);
1561       faceuv = osface_final[findex_dst].uv;
1562
1563       /* check that this intersects - Its possible this misses :/ -
1564        * could also check its not between */
1565       if (mtessface_final[findex_dst].v4) {
1566         if (isect_point_quad_v2(uv, faceuv[0], faceuv[1], faceuv[2], faceuv[3])) {
1567           return findex_dst;
1568         }
1569       }
1570       else if (isect_point_tri_v2(uv, faceuv[0], faceuv[1], faceuv[2])) {
1571         return findex_dst;
1572       }
1573     }
1574   }
1575   else { /* if we have no node, try every face */
1576     for (int findex_dst = 0; findex_dst < totface_final; findex_dst++) {
1577       /* If current tessface from 'final' DM and orig tessface (given by index) map to the same orig poly... */
1578       if (BKE_mesh_origindex_mface_mpoly(index_mf_to_mpoly, index_mp_to_orig, findex_dst) ==
1579           pindex_orig) {
1580         faceuv = osface_final[findex_dst].uv;
1581
1582         /* check that this intersects - Its possible this misses :/ -
1583          * could also check its not between */
1584         if (mtessface_final[findex_dst].v4) {
1585           if (isect_point_quad_v2(uv, faceuv[0], faceuv[1], faceuv[2], faceuv[3])) {
1586             return findex_dst;
1587           }
1588         }
1589         else if (isect_point_tri_v2(uv, faceuv[0], faceuv[1], faceuv[2])) {
1590           return findex_dst;
1591         }
1592       }
1593     }
1594   }
1595
1596   return DMCACHE_NOTFOUND;
1597 }
1598
1599 static int psys_map_index_on_dm(Mesh *mesh,
1600                                 int from,
1601                                 int index,
1602                                 int index_dmcache,
1603                                 const float fw[4],
1604                                 float UNUSED(foffset),
1605                                 int *mapindex,
1606                                 float mapfw[4])
1607 {
1608   if (index < 0) {
1609     return 0;
1610   }
1611
1612   if (mesh->runtime.deformed_only || index_dmcache == DMCACHE_ISCHILD) {
1613     /* for meshes that are either only deformed or for child particles, the
1614      * index and fw do not require any mapping, so we can directly use it */
1615     if (from == PART_FROM_VERT) {
1616       if (index >= mesh->totvert) {
1617         return 0;
1618       }
1619
1620       *mapindex = index;
1621     }
1622     else { /* FROM_FACE/FROM_VOLUME */
1623       if (index >= mesh->totface) {
1624         return 0;
1625       }
1626
1627       *mapindex = index;
1628       copy_v4_v4(mapfw, fw);
1629     }
1630   }
1631   else {
1632     /* for other meshes that have been modified, we try to map the particle
1633      * to their new location, which means a different index, and for faces
1634      * also a new face interpolation weights */
1635     if (from == PART_FROM_VERT) {
1636       if (index_dmcache == DMCACHE_NOTFOUND || index_dmcache > mesh->totvert) {
1637         return 0;
1638       }
1639
1640       *mapindex = index_dmcache;
1641     }
1642     else { /* FROM_FACE/FROM_VOLUME */
1643            /* find a face on the derived mesh that uses this face */
1644       MFace *mface;
1645       OrigSpaceFace *osface;
1646       int i;
1647
1648       i = index_dmcache;
1649
1650       if (i == DMCACHE_NOTFOUND || i >= mesh->totface) {
1651         return 0;
1652       }
1653
1654       *mapindex = i;
1655
1656       /* modify the original weights to become
1657        * weights for the derived mesh face */
1658       osface = CustomData_get_layer(&mesh->fdata, CD_ORIGSPACE);
1659       mface = &mesh->mface[i];
1660
1661       if (osface == NULL) {
1662         mapfw[0] = mapfw[1] = mapfw[2] = mapfw[3] = 0.0f;
1663       }
1664       else {
1665         psys_origspace_to_w(&osface[i], mface->v4, fw, mapfw);
1666       }
1667     }
1668   }
1669
1670   return 1;
1671 }
1672
1673 /* interprets particle data to get a point on a mesh in object space */
1674 void psys_particle_on_dm(Mesh *mesh_final,
1675                          int from,
1676                          int index,
1677                          int index_dmcache,
1678                          const float fw[4],
1679                          float foffset,
1680                          float vec[3],
1681                          float nor[3],
1682                          float utan[3],
1683                          float vtan[3],
1684                          float orco[3])
1685 {
1686   float tmpnor[3], mapfw[4];
1687   float(*orcodata)[3];
1688   int mapindex;
1689
1690   if (!psys_map_index_on_dm(
1691           mesh_final, from, index, index_dmcache, fw, foffset, &mapindex, mapfw)) {
1692     if (vec) {
1693       vec[0] = vec[1] = vec[2] = 0.0;
1694     }
1695     if (nor) {
1696       nor[0] = nor[1] = 0.0;
1697       nor[2] = 1.0;
1698     }
1699     if (orco) {
1700       orco[0] = orco[1] = orco[2] = 0.0;
1701     }
1702     if (utan) {
1703       utan[0] = utan[1] = utan[2] = 0.0;
1704     }
1705     if (vtan) {
1706       vtan[0] = vtan[1] = vtan[2] = 0.0;
1707     }
1708
1709     return;
1710   }
1711
1712   orcodata = CustomData_get_layer(&mesh_final->vdata, CD_ORCO);
1713
1714   if (from == PART_FROM_VERT) {
1715     copy_v3_v3(vec, mesh_final->mvert[mapindex].co);
1716
1717     if (nor) {
1718       normal_short_to_float_v3(nor, mesh_final->mvert[mapindex].no);
1719       normalize_v3(nor);
1720     }
1721
1722     if (orco) {
1723       if (orcodata) {
1724         copy_v3_v3(orco, orcodata[mapindex]);
1725       }
1726       else {
1727         copy_v3_v3(orco, vec);
1728       }
1729     }
1730
1731     if (utan && vtan) {
1732       utan[0] = utan[1] = utan[2] = 0.0f;
1733       vtan[0] = vtan[1] = vtan[2] = 0.0f;
1734     }
1735   }
1736   else { /* PART_FROM_FACE / PART_FROM_VOLUME */
1737     MFace *mface;
1738     MTFace *mtface;
1739     MVert *mvert;
1740
1741     mface = &mesh_final->mface[mapindex];
1742     mvert = mesh_final->mvert;
1743     mtface = mesh_final->mtface;
1744
1745     if (mtface) {
1746       mtface += mapindex;
1747     }
1748
1749     if (from == PART_FROM_VOLUME) {
1750       psys_interpolate_face(mvert, mface, mtface, orcodata, mapfw, vec, tmpnor, utan, vtan, orco);
1751       if (nor) {
1752         copy_v3_v3(nor, tmpnor);
1753       }
1754
1755       normalize_v3(
1756           tmpnor); /* XXX Why not normalize tmpnor before copying it into nor??? -- mont29 */
1757       mul_v3_fl(tmpnor, -foffset);
1758       add_v3_v3(vec, tmpnor);
1759     }
1760     else {
1761       psys_interpolate_face(mvert, mface, mtface, orcodata, mapfw, vec, nor, utan, vtan, orco);
1762     }
1763   }
1764 }
1765
1766 float psys_particle_value_from_verts(Mesh *mesh, short from, ParticleData *pa, float *values)
1767 {
1768   float mapfw[4];
1769   int mapindex;
1770
1771   if (!psys_map_index_on_dm(
1772           mesh, from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, &mapindex, mapfw)) {
1773     return 0.0f;
1774   }
1775
1776   return psys_interpolate_value_from_verts(mesh, from, mapindex, mapfw, values);
1777 }
1778
1779 ParticleSystemModifierData *psys_get_modifier(Object *ob, ParticleSystem *psys)
1780 {
1781   ModifierData *md;
1782   ParticleSystemModifierData *psmd;
1783
1784   for (md = ob->modifiers.first; md; md = md->next) {
1785     if (md->type == eModifierType_ParticleSystem) {
1786       psmd = (ParticleSystemModifierData *)md;
1787       if (psmd->psys == psys) {
1788         return psmd;
1789       }
1790     }
1791   }
1792   return NULL;
1793 }
1794 /************************************************/
1795 /*          Particles on a shape                */
1796 /************************************************/
1797 /* ready for future use */
1798 static void psys_particle_on_shape(int UNUSED(distr),
1799                                    int UNUSED(index),
1800                                    float *UNUSED(fuv),
1801                                    float vec[3],
1802                                    float nor[3],
1803                                    float utan[3],
1804                                    float vtan[3],
1805                                    float orco[3])
1806 {
1807   /* TODO */
1808   float zerovec[3] = {0.0f, 0.0f, 0.0f};
1809   if (vec) {
1810     copy_v3_v3(vec, zerovec);
1811   }
1812   if (nor) {
1813     copy_v3_v3(nor, zerovec);
1814   }
1815   if (utan) {
1816     copy_v3_v3(utan, zerovec);
1817   }
1818   if (vtan) {
1819     copy_v3_v3(vtan, zerovec);
1820   }
1821   if (orco) {
1822     copy_v3_v3(orco, zerovec);
1823   }
1824 }
1825 /************************************************/
1826 /*          Particles on emitter                */
1827 /************************************************/
1828
1829 void psys_emitter_customdata_mask(ParticleSystem *psys, CustomData_MeshMasks *r_cddata_masks)
1830 {
1831   MTex *mtex;
1832   int i;
1833
1834   if (!psys->part) {
1835     return;
1836   }
1837
1838   for (i = 0; i < MAX_MTEX; i++) {
1839     mtex = psys->part->mtex[i];
1840     if (mtex && mtex->mapto && (mtex->texco & TEXCO_UV)) {
1841       r_cddata_masks->fmask |= CD_MASK_MTFACE;
1842     }
1843   }
1844
1845   if (psys->part->tanfac != 0.0f) {
1846     r_cddata_masks->fmask |= CD_MASK_MTFACE;
1847   }
1848
1849   /* ask for vertexgroups if we need them */
1850   for (i = 0; i < PSYS_TOT_VG; i++) {
1851     if (psys->vgroup[i]) {
1852       r_cddata_masks->vmask |= CD_MASK_MDEFORMVERT;
1853       break;
1854     }
1855   }
1856
1857   /* particles only need this if they are after a non deform modifier, and
1858    * the modifier stack will only create them in that case. */
1859   r_cddata_masks->lmask |= CD_MASK_ORIGSPACE_MLOOP;
1860   /* XXX Check we do need all those? */
1861   r_cddata_masks->vmask |= CD_MASK_ORIGINDEX;
1862   r_cddata_masks->emask |= CD_MASK_ORIGINDEX;
1863   r_cddata_masks->pmask |= CD_MASK_ORIGINDEX;
1864
1865   r_cddata_masks->vmask |= CD_MASK_ORCO;
1866 }
1867
1868 void psys_particle_on_emitter(ParticleSystemModifierData *psmd,
1869                               int from,
1870                               int index,
1871                               int index_dmcache,
1872                               float fuv[4],
1873                               float foffset,
1874                               float vec[3],
1875                               float nor[3],
1876                               float utan[3],
1877                               float vtan[3],
1878                               float orco[3])
1879 {
1880   if (psmd && psmd->mesh_final) {
1881     if (psmd->psys->part->distr == PART_DISTR_GRID && psmd->psys->part->from != PART_FROM_VERT) {
1882       if (vec) {
1883         copy_v3_v3(vec, fuv);
1884       }
1885
1886       if (orco) {
1887         copy_v3_v3(orco, fuv);
1888       }
1889       return;
1890     }
1891     /* we cant use the num_dmcache */
1892     psys_particle_on_dm(
1893         psmd->mesh_final, from, index, index_dmcache, fuv, foffset, vec, nor, utan, vtan, orco);
1894   }
1895   else {
1896     psys_particle_on_shape(from, index, fuv, vec, nor, utan, vtan, orco);
1897   }
1898 }
1899 /************************************************/
1900 /*          Path Cache                          */
1901 /************************************************/
1902
1903 void precalc_guides(ParticleSimulationData *sim, ListBase *effectors)
1904 {
1905   EffectedPoint point;
1906   ParticleKey state;
1907   EffectorData efd;
1908   EffectorCache *eff;
1909   ParticleSystem *psys = sim->psys;
1910   EffectorWeights *weights = sim->psys->part->effector_weights;
1911   GuideEffectorData *data;
1912   PARTICLE_P;
1913
1914   if (!effectors) {
1915     return;
1916   }
1917
1918   LOOP_PARTICLES
1919   {
1920     psys_particle_on_emitter(sim->psmd,
1921                              sim->psys->part->from,
1922                              pa->num,
1923                              pa->num_dmcache,
1924                              pa->fuv,
1925                              pa->foffset,
1926                              state.co,
1927                              0,
1928                              0,
1929                              0,
1930                              0);
1931
1932     mul_m4_v3(sim->ob->obmat, state.co);
1933     mul_mat3_m4_v3(sim->ob->obmat, state.vel);
1934
1935     pd_point_from_particle(sim, pa, &state, &point);
1936
1937     for (eff = effectors->first; eff; eff = eff->next) {
1938       if (eff->pd->forcefield != PFIELD_GUIDE) {
1939         continue;
1940       }
1941
1942       if (!eff->guide_data) {
1943         eff->guide_data = MEM_callocN(sizeof(GuideEffectorData) * psys->totpart,
1944                                       "GuideEffectorData");
1945       }
1946
1947       data = eff->guide_data + p;
1948
1949       sub_v3_v3v3(efd.vec_to_point, state.co, eff->guide_loc);
1950       copy_v3_v3(efd.nor, eff->guide_dir);
1951       efd.distance = len_v3(efd.vec_to_point);
1952
1953       copy_v3_v3(data->vec_to_point, efd.vec_to_point);
1954       data->strength = effector_falloff(eff, &efd, &point, weights);
1955     }
1956   }
1957 }
1958
1959 int do_guides(Depsgraph *depsgraph,
1960               ParticleSettings *part,
1961               ListBase *effectors,
1962               ParticleKey *state,
1963               int index,
1964               float time)
1965 {
1966   CurveMapping *clumpcurve = (part->child_flag & PART_CHILD_USE_CLUMP_CURVE) ? part->clumpcurve :
1967                                                                                NULL;
1968   CurveMapping *roughcurve = (part->child_flag & PART_CHILD_USE_ROUGH_CURVE) ? part->roughcurve :
1969                                                                                NULL;
1970   EffectorCache *eff;
1971   PartDeflect *pd;
1972   Curve *cu;
1973   GuideEffectorData *data;
1974
1975   float effect[3] = {0.0f, 0.0f, 0.0f}, veffect[3] = {0.0f, 0.0f, 0.0f};
1976   float guidevec[4], guidedir[3], rot2[4], temp[3];
1977   float guidetime, radius, weight, angle, totstrength = 0.0f;
1978   float vec_to_point[3];
1979
1980   if (effectors) {
1981     for (eff = effectors->first; eff; eff = eff->next) {
1982       pd = eff->pd;
1983
1984       if (pd->forcefield != PFIELD_GUIDE) {
1985         continue;
1986       }
1987
1988       data = eff->guide_data + index;
1989
1990       if (data->strength <= 0.0f) {
1991         continue;
1992       }
1993
1994       guidetime = time / (1.0f - pd->free_end);
1995
1996       if (guidetime > 1.0f) {
1997         continue;
1998       }
1999
2000       cu = (Curve *)eff->ob->data;
2001
2002       if (pd->flag & PFIELD_GUIDE_PATH_ADD) {
2003         if (where_on_path(
2004                 eff->ob, data->strength * guidetime, guidevec, guidedir, NULL, &radius, &weight) ==
2005             0) {
2006           return 0;
2007         }
2008       }
2009       else {
2010         if (where_on_path(eff->ob, guidetime, guidevec, guidedir, NULL, &radius, &weight) == 0) {
2011           return 0;
2012         }
2013       }
2014
2015       mul_m4_v3(eff->ob->obmat, guidevec);
2016       mul_mat3_m4_v3(eff->ob->obmat, guidedir);
2017
2018       normalize_v3(guidedir);
2019
2020       copy_v3_v3(vec_to_point, data->vec_to_point);
2021
2022       if (guidetime != 0.0f) {
2023         /* curve direction */
2024         cross_v3_v3v3(temp, eff->guide_dir, guidedir);
2025         angle = dot_v3v3(eff->guide_dir, guidedir) / (len_v3(eff->guide_dir));
2026         angle = saacos(angle);
2027         axis_angle_to_quat(rot2, temp, angle);
2028         mul_qt_v3(rot2, vec_to_point);
2029
2030         /* curve tilt */
2031         axis_angle_to_quat(rot2, guidedir, guidevec[3] - eff->guide_loc[3]);
2032         mul_qt_v3(rot2, vec_to_point);
2033       }
2034
2035       /* curve taper */
2036       if (cu->taperobj) {
2037         mul_v3_fl(vec_to_point,
2038                   BKE_displist_calc_taper(depsgraph,
2039                                           eff->scene,
2040                                           cu->taperobj,
2041                                           (int)(data->strength * guidetime * 100.0f),
2042                                           100));
2043       }
2044       else { /* curve size*/
2045         if (cu->flag & CU_PATH_RADIUS) {
2046           mul_v3_fl(vec_to_point, radius);
2047         }
2048       }
2049
2050       if (clumpcurve) {
2051         curvemapping_changed_all(clumpcurve);
2052       }
2053       if (roughcurve) {
2054         curvemapping_changed_all(roughcurve);
2055       }
2056
2057       {
2058         ParticleKey key;
2059         float par_co[3] = {0.0f, 0.0f, 0.0f};
2060         float par_vel[3] = {0.0f, 0.0f, 0.0f};
2061         float par_rot[4] = {1.0f, 0.0f, 0.0f, 0.0f};
2062         float orco_offset[3] = {0.0f, 0.0f, 0.0f};
2063
2064         copy_v3_v3(key.co, vec_to_point);
2065         do_kink(&key,
2066                 par_co,
2067                 par_vel,
2068                 par_rot,
2069                 guidetime,
2070                 pd->kink_freq,
2071                 pd->kink_shape,
2072                 pd->kink_amp,
2073                 0.f,
2074                 pd->kink,
2075                 pd->kink_axis,
2076                 0,
2077                 0);
2078         do_clump(&key,
2079                  par_co,
2080                  guidetime,
2081                  orco_offset,
2082                  pd->clump_fac,
2083                  pd->clump_pow,
2084                  1.0f,
2085                  part->child_flag & PART_CHILD_USE_CLUMP_NOISE,
2086                  part->clump_noise_size,
2087                  clumpcurve);
2088         copy_v3_v3(vec_to_point, key.co);
2089       }
2090
2091       add_v3_v3(vec_to_point, guidevec);
2092
2093       //sub_v3_v3v3(pa_loc, pa_loc, pa_zero);
2094       madd_v3_v3fl(effect, vec_to_point, data->strength);
2095       madd_v3_v3fl(veffect, guidedir, data->strength);
2096       totstrength += data->strength;
2097
2098       if (pd->flag & PFIELD_GUIDE_PATH_WEIGHT) {
2099         totstrength *= weight;
2100       }
2101     }
2102   }
2103
2104   if (totstrength != 0.0f) {
2105     if (totstrength > 1.0f) {
2106       mul_v3_fl(effect, 1.0f / totstrength);
2107     }
2108     CLAMP(totstrength, 0.0f, 1.0f);
2109     //add_v3_v3(effect, pa_zero);
2110     interp_v3_v3v3(state->co, state->co, effect, totstrength);
2111
2112     normalize_v3(veffect);
2113     mul_v3_fl(veffect, len_v3(state->vel));
2114     copy_v3_v3(state->vel, veffect);
2115     return 1;
2116   }
2117   return 0;
2118 }
2119
2120 static void do_path_effectors(ParticleSimulationData *sim,
2121                               int i,
2122                               ParticleCacheKey *ca,
2123                               int k,
2124                               int steps,
2125                               float *UNUSED(rootco),
2126                               float effector,
2127                               float UNUSED(dfra),
2128                               float UNUSED(cfra),
2129                               float *length,
2130                               float *vec)
2131 {
2132   float force[3] = {0.0f, 0.0f, 0.0f};
2133   ParticleKey eff_key;
2134   EffectedPoint epoint;
2135
2136   /* Don't apply effectors for dynamic hair, otherwise the effectors don't get applied twice. */
2137   if (sim->psys->flag & PSYS_HAIR_DYNAMICS) {
2138     return;
2139   }
2140
2141   copy_v3_v3(eff_key.co, (ca - 1)->co);
2142   copy_v3_v3(eff_key.vel, (ca - 1)->vel);
2143   copy_qt_qt(eff_key.rot, (ca - 1)->rot);
2144
2145   pd_point_from_particle(sim, sim->psys->particles + i, &eff_key, &epoint);
2146   BKE_effectors_apply(sim->psys->effectors,
2147                       sim->colliders,
2148                       sim->psys->part->effector_weights,
2149                       &epoint,
2150                       force,
2151                       NULL);
2152
2153   mul_v3_fl(force,
2154             effector * powf((float)k / (float)steps, 100.0f * sim->psys->part->eff_hair) /
2155                 (float)steps);
2156
2157   add_v3_v3(force, vec);
2158
2159   normalize_v3(force);
2160
2161   if (k < steps) {
2162     sub_v3_v3v3(vec, (ca + 1)->co, ca->co);
2163   }
2164
2165   madd_v3_v3v3fl(ca->co, (ca - 1)->co, force, *length);
2166
2167   if (k < steps) {
2168     *length = len_v3(vec);
2169   }
2170 }
2171 static void offset_child(ChildParticle *cpa,
2172                          ParticleKey *par,
2173                          float *par_rot,
2174                          ParticleKey *child,
2175                          float flat,
2176                          float radius)
2177 {
2178   copy_v3_v3(child->co, cpa->fuv);
2179   mul_v3_fl(child->co, radius);
2180
2181   child->co[0] *= flat;
2182
2183   copy_v3_v3(child->vel, par->vel);
2184
2185   if (par_rot) {
2186     mul_qt_v3(par_rot, child->co);
2187     copy_qt_qt(child->rot, par_rot);
2188   }
2189   else {
2190     unit_qt(child->rot);
2191   }
2192
2193   add_v3_v3(child->co, par->co);
2194 }
2195 float *psys_cache_vgroup(Mesh *mesh, ParticleSystem *psys, int vgroup)
2196 {
2197   float *vg = 0;
2198
2199   if (vgroup < 0) {
2200     /* hair dynamics pinning vgroup */
2201   }
2202   else if (psys->vgroup[vgroup]) {
2203     MDeformVert *dvert = mesh->dvert;
2204     if (dvert) {
2205       int totvert = mesh->totvert, i;
2206       vg = MEM_callocN(sizeof(float) * totvert, "vg_cache");
2207       if (psys->vg_neg & (1 << vgroup)) {
2208         for (i = 0; i < totvert; i++) {
2209           vg[i] = 1.0f - defvert_find_weight(&dvert[i], psys->vgroup[vgroup] - 1);
2210         }
2211       }
2212       else {
2213         for (i = 0; i < totvert; i++) {
2214           vg[i] = defvert_find_weight(&dvert[i], psys->vgroup[vgroup] - 1);
2215         }
2216       }
2217     }
2218   }
2219   return vg;
2220 }
2221 void psys_find_parents(ParticleSimulationData *sim, const bool use_render_params)
2222 {
2223   ParticleSystem *psys = sim->psys;
2224   ParticleSettings *part = sim->psys->part;
2225   KDTree_3d *tree;
2226   ChildParticle *cpa;
2227   ParticleTexture ptex;
2228   int p, totparent, totchild = sim->psys->totchild;
2229   float co[3], orco[3];
2230   int from = PART_FROM_FACE;
2231   totparent = (int)(totchild * part->parents * 0.3f);
2232
2233   if (use_render_params && part->child_nbr && part->ren_child_nbr) {
2234     totparent *= (float)part->child_nbr / (float)part->ren_child_nbr;
2235   }
2236
2237   /* hard limit, workaround for it being ignored above */
2238   if (sim->psys->totpart < totparent) {
2239     totparent = sim->psys->totpart;
2240   }
2241
2242   tree = BLI_kdtree_3d_new(totparent);
2243
2244   for (p = 0, cpa = sim->psys->child; p < totparent; p++, cpa++) {
2245     psys_particle_on_emitter(
2246         sim->psmd, from, cpa->num, DMCACHE_ISCHILD, cpa->fuv, cpa->foffset, co, 0, 0, 0, orco);
2247
2248     /* Check if particle doesn't exist because of texture influence. Insert only existing particles into kdtree. */
2249     get_cpa_texture(sim->psmd->mesh_final,
2250                     psys,
2251                     part,
2252                     psys->particles + cpa->pa[0],
2253                     p,
2254                     cpa->num,
2255                     cpa->fuv,
2256                     orco,
2257                     &ptex,
2258                     PAMAP_DENS | PAMAP_CHILD,
2259                     psys->cfra);
2260
2261     if (ptex.exist >= psys_frand(psys, p + 24)) {
2262       BLI_kdtree_3d_insert(tree, p, orco);
2263     }
2264   }
2265
2266   BLI_kdtree_3d_balance(tree);
2267
2268   for (; p < totchild; p++, cpa++) {
2269     psys_particle_on_emitter(
2270         sim->psmd, from, cpa->num, DMCACHE_ISCHILD, cpa->fuv, cpa->foffset, co, 0, 0, 0, orco);
2271     cpa->parent = BLI_kdtree_3d_find_nearest(tree, orco, NULL);
2272   }
2273
2274   BLI_kdtree_3d_free(tree);
2275 }
2276
2277 static bool psys_thread_context_init_path(ParticleThreadContext *ctx,
2278                                           ParticleSimulationData *sim,
2279                                           Scene *scene,
2280                                           float cfra,
2281                                           const bool editupdate,
2282                                           const bool use_render_params)
2283 {
2284   ParticleSystem *psys = sim->psys;
2285   ParticleSettings *part = psys->part;
2286   int totparent = 0, between = 0;
2287   int segments = 1 << part->draw_step;
2288   int totchild = psys->totchild;
2289
2290   psys_thread_context_init(ctx, sim);
2291
2292   /*---start figuring out what is actually wanted---*/
2293   if (psys_in_edit_mode(sim->depsgraph, psys)) {
2294     ParticleEditSettings *pset = &scene->toolsettings->particle;
2295
2296     if ((use_render_params == 0) &&
2297         (psys_orig_edit_get(psys) == NULL || pset->flag & PE_DRAW_PART) == 0) {
2298       totchild = 0;
2299     }
2300
2301     segments = 1 << pset->draw_step;
2302   }
2303
2304   if (totchild && part->childtype == PART_CHILD_FACES) {
2305     totparent = (int)(totchild * part->parents * 0.3f);
2306
2307     if (use_render_params && part->child_nbr && part->ren_child_nbr) {
2308       totparent *= (float)part->child_nbr / (float)part->ren_child_nbr;
2309     }
2310
2311     /* part->parents could still be 0 so we can't test with totparent */
2312     between = 1;
2313   }
2314
2315   if (use_render_params) {
2316     segments = 1 << part->ren_step;
2317   }
2318   else {
2319     totchild = (int)((float)totchild * (float)part->disp / 100.0f);
2320     totparent = MIN2(totparent, totchild);
2321   }
2322
2323   if (totchild == 0) {
2324     return false;
2325   }
2326
2327   /* fill context values */
2328   ctx->between = between;
2329   ctx->segments = segments;
2330   if (ELEM(part->kink, PART_KINK_SPIRAL)) {
2331     ctx->extra_segments = max_ii(part->kink_extra_steps, 1);
2332   }
2333   else {
2334     ctx->extra_segments = 0;
2335   }
2336   ctx->totchild = totchild;
2337   ctx->totparent = totparent;
2338   ctx->parent_pass = 0;
2339   ctx->cfra = cfra;
2340   ctx->editupdate = editupdate;
2341
2342   psys->lattice_deform_data = psys_create_lattice_deform_data(&ctx->sim);
2343
2344   /* cache all relevant vertex groups if they exist */
2345   ctx->vg_length = psys_cache_vgroup(ctx->mesh, psys, PSYS_VG_LENGTH);
2346   ctx->vg_clump = psys_cache_vgroup(ctx->mesh, psys, PSYS_VG_CLUMP);
2347   ctx->vg_kink = psys_cache_vgroup(ctx->mesh, psys, PSYS_VG_KINK);
2348   ctx->vg_rough1 = psys_cache_vgroup(ctx->mesh, psys, PSYS_VG_ROUGH1);
2349   ctx->vg_rough2 = psys_cache_vgroup(ctx->mesh, psys, PSYS_VG_ROUGH2);
2350   ctx->vg_roughe = psys_cache_vgroup(ctx->mesh, psys, PSYS_VG_ROUGHE);
2351   ctx->vg_twist = psys_cache_vgroup(ctx->mesh, psys, PSYS_VG_TWIST);
2352   if (psys->part->flag & PART_CHILD_EFFECT) {
2353     ctx->vg_effector = psys_cache_vgroup(ctx->mesh, psys, PSYS_VG_EFFECTOR);
2354   }
2355
2356   /* prepare curvemapping tables */
2357   if ((part->child_flag & PART_CHILD_USE_CLUMP_CURVE) && part->clumpcurve) {
2358     ctx->clumpcurve = curvemapping_copy(part->clumpcurve);
2359     curvemapping_changed_all(ctx->clumpcurve);
2360   }
2361   else {
2362     ctx->clumpcurve = NULL;
2363   }
2364   if ((part->child_flag & PART_CHILD_USE_ROUGH_CURVE) && part->roughcurve) {
2365     ctx->roughcurve = curvemapping_copy(part->roughcurve);
2366     curvemapping_changed_all(ctx->roughcurve);
2367   }
2368   else {
2369     ctx->roughcurve = NULL;
2370   }
2371   if ((part->child_flag & PART_CHILD_USE_TWIST_CURVE) && part->twistcurve) {
2372     ctx->twistcurve = curvemapping_copy(part->twistcurve);
2373     curvemapping_changed_all(ctx->twistcurve);
2374   }
2375   else {
2376     ctx->twistcurve = NULL;
2377   }
2378
2379   return true;
2380 }
2381
2382 static void psys_task_init_path(ParticleTask *task, ParticleSimulationData *sim)
2383 {
2384   /* init random number generator */
2385   int seed = 31415926 + sim->psys->seed;
2386
2387   task->rng_path = BLI_rng_new(seed);
2388 }
2389
2390 /* note: this function must be thread safe, except for branching! */
2391 static void psys_thread_create_path(ParticleTask *task,
2392                                     struct ChildParticle *cpa,
2393                                     ParticleCacheKey *child_keys,
2394                                     int i)
2395 {
2396   ParticleThreadContext *ctx = task->ctx;
2397   Object *ob = ctx->sim.ob;
2398   ParticleSystem *psys = ctx->sim.psys;
2399   ParticleSettings *part = psys->part;
2400   ParticleCacheKey **cache = psys->childcache;
2401   PTCacheEdit *edit = psys_orig_edit_get(psys);
2402   ParticleCacheKey **pcache = psys_in_edit_mode(ctx->sim.depsgraph, psys) && edit ?
2403                                   edit->pathcache :
2404                                   psys->pathcache;
2405   ParticleCacheKey *child, *key[4];
2406   ParticleTexture ptex;
2407   float *cpa_fuv = 0, *par_rot = 0, rot[4];
2408   float orco[3], hairmat[4][4], dvec[3], off1[4][3], off2[4][3];
2409   float eff_length, eff_vec[3], weight[4];
2410   int k, cpa_num;
2411   short cpa_from;
2412
2413   if (!pcache) {
2414     return;
2415   }
2416
2417   if (ctx->between) {
2418     ParticleData *pa = psys->particles + cpa->pa[0];
2419     int w, needupdate;
2420     float foffset, wsum = 0.f;
2421     float co[3];
2422     float p_min = part->parting_min;
2423     float p_max = part->parting_max;
2424     /* Virtual parents don't work nicely with parting. */
2425     float p_fac = part->parents > 0.f ? 0.f : part->parting_fac;
2426
2427     if (ctx->editupdate) {
2428       needupdate = 0;
2429       w = 0;
2430       while (w < 4 && cpa->pa[w] >= 0) {
2431         if (edit->points[cpa->pa[w]].flag & PEP_EDIT_RECALC) {
2432           needupdate = 1;
2433           break;
2434         }
2435         w++;
2436       }
2437
2438       if (!needupdate) {
2439         return;
2440       }
2441       else {
2442         memset(child_keys, 0, sizeof(*child_keys) * (ctx->segments + 1));
2443       }
2444     }
2445
2446     /* get parent paths */
2447     for (w = 0; w < 4; w++) {
2448       if (cpa->pa[w] >= 0) {
2449         key[w] = pcache[cpa->pa[w]];
2450         weight[w] = cpa->w[w];
2451       }
2452       else {
2453         key[w] = pcache[0];
2454         weight[w] = 0.f;
2455       }
2456     }
2457
2458     /* modify weights to create parting */
2459     if (p_fac > 0.f) {
2460       const ParticleCacheKey *key_0_last = pcache_key_segment_endpoint_safe(key[0]);
2461       for (w = 0; w < 4; w++) {
2462         if (w && (weight[w] > 0.f)) {
2463           const ParticleCacheKey *key_w_last = pcache_key_segment_endpoint_safe(key[w]);
2464           float d;
2465           if (part->flag & PART_CHILD_LONG_HAIR) {
2466             /* For long hair use tip distance/root distance as parting factor instead of root to tip angle. */
2467             float d1 = len_v3v3(key[0]->co, key[w]->co);
2468             float d2 = len_v3v3(key_0_last->co, key_w_last->co);
2469
2470             d = d1 > 0.f ? d2 / d1 - 1.f : 10000.f;
2471           }
2472           else {
2473             float v1[3], v2[3];
2474             sub_v3_v3v3(v1, key_0_last->co, key[0]->co);
2475             sub_v3_v3v3(v2, key_w_last->co, key[w]->co);
2476             normalize_v3(v1);
2477             normalize_v3(v2);
2478
2479             d = RAD2DEGF(saacos(dot_v3v3(v1, v2)));
2480           }
2481
2482           if (p_max > p_min) {
2483             d = (d - p_min) / (p_max - p_min);
2484           }
2485           else {
2486             d = (d - p_min) <= 0.f ? 0.f : 1.f;
2487           }
2488
2489           CLAMP(d, 0.f, 1.f);
2490
2491           if (d > 0.f) {
2492             weight[w] *= (1.f - d);
2493           }
2494         }
2495         wsum += weight[w];
2496       }
2497       for (w = 0; w < 4; w++) {
2498         weight[w] /= wsum;
2499       }
2500
2501       interp_v4_v4v4(weight, cpa->w, weight, p_fac);
2502     }
2503
2504     /* get the original coordinates (orco) for texture usage */
2505     cpa_num = cpa->num;
2506
2507     foffset = cpa->foffset;
2508     cpa_fuv = cpa->fuv;
2509     cpa_from = PART_FROM_FACE;
2510
2511     psys_particle_on_emitter(
2512         ctx->sim.psmd, cpa_from, cpa_num, DMCACHE_ISCHILD, cpa->fuv, foffset, co, 0, 0, 0, orco);
2513
2514     mul_m4_v3(ob->obmat, co);
2515
2516     for (w = 0; w < 4; w++) {
2517       sub_v3_v3v3(off1[w], co, key[w]->co);
2518     }
2519
2520     psys_mat_hair_to_global(ob, ctx->sim.psmd->mesh_final, psys->part->from, pa, hairmat);
2521   }
2522   else {
2523     ParticleData *pa = psys->particles + cpa->parent;
2524     float co[3];
2525     if (ctx->editupdate) {
2526       if (!(edit->points[cpa->parent].flag & PEP_EDIT_RECALC)) {
2527         return;
2528       }
2529
2530       memset(child_keys, 0, sizeof(*child_keys) * (ctx->segments + 1));
2531     }
2532
2533     /* get the parent path */
2534     key[0] = pcache[cpa->parent];
2535
2536     /* get the original coordinates (orco) for texture usage */
2537     cpa_from = part->from;
2538
2539     /*
2540      * NOTE: Should in theory be the same as:
2541      * cpa_num = psys_particle_dm_face_lookup(
2542      *        ctx->sim.psmd->dm_final,
2543      *        ctx->sim.psmd->dm_deformed,
2544      *        pa->num, pa->fuv,
2545      *        NULL);
2546      */
2547     cpa_num = (ELEM(pa->num_dmcache, DMCACHE_ISCHILD, DMCACHE_NOTFOUND)) ? pa->num :
2548                                                                            pa->num_dmcache;
2549
2550     /* XXX hack to avoid messed up particle num and subsequent crash (#40733) */
2551     if (cpa_num > ctx->sim.psmd->mesh_final->totface) {
2552       cpa_num = 0;
2553     }
2554     cpa_fuv = pa->fuv;
2555
2556     psys_particle_on_emitter(ctx->sim.psmd,
2557                              cpa_from,
2558                              cpa_num,
2559                              DMCACHE_ISCHILD,
2560                              cpa_fuv,
2561                              pa->foffset,
2562                              co,
2563                              0,
2564                              0,
2565                              0,
2566                              orco);
2567
2568     psys_mat_hair_to_global(ob, ctx->sim.psmd->mesh_final, psys->part->from, pa, hairmat);
2569   }
2570
2571   child_keys->segments = ctx->segments;
2572
2573   /* get different child parameters from textures & vgroups */
2574   get_child_modifier_parameters(part, ctx, cpa, cpa_from, cpa_num, cpa_fuv, orco, &ptex);
2575
2576   if (ptex.exist < psys_frand(psys, i + 24)) {
2577     child_keys->segments = -1;
2578     return;
2579   }
2580
2581   /* create the child path */
2582   for (k = 0, child = child_keys; k <= ctx->segments; k++, child++) {
2583     if (ctx->between) {
2584       int w = 0;
2585
2586       zero_v3(child->co);
2587       zero_v3(child->vel);
2588       unit_qt(child->rot);
2589
2590       for (w = 0; w < 4; w++) {
2591         copy_v3_v3(off2[w], off1[w]);
2592
2593         if (part->flag & PART_CHILD_LONG_HAIR) {
2594           /* Use parent rotation (in addition to emission location) to determine child offset. */
2595           if (k) {
2596             mul_qt_v3((key[w] + k)->rot, off2[w]);
2597           }
2598
2599           /* Fade the effect of rotation for even lengths in the end */
2600           project_v3_v3v3(dvec, off2[w], (key[w] + k)->vel);
2601           madd_v3_v3fl(off2[w], dvec, -(float)k / (float)ctx->segments);
2602         }
2603
2604         add_v3_v3(off2[w], (key[w] + k)->co);
2605       }
2606
2607       /* child position is the weighted sum of parent positions */
2608       interp_v3_v3v3v3v3(child->co, off2[0], off2[1], off2[2], off2[3], weight);
2609       interp_v3_v3v3v3v3(child->vel,
2610                          (key[0] + k)->vel,
2611                          (key[1] + k)->vel,
2612                          (key[2] + k)->vel,
2613                          (key[3] + k)->vel,
2614                          weight);
2615
2616       copy_qt_qt(child->rot, (key[0] + k)->rot);
2617     }
2618     else {
2619       if (k) {
2620         mul_qt_qtqt(rot, (key[0] + k)->rot, key[0]->rot);
2621         par_rot = rot;
2622       }
2623       else {
2624         par_rot = key[0]->rot;
2625       }
2626       /* offset the child from the parent position */
2627       offset_child(cpa,
2628                    (ParticleKey *)(key[0] + k),
2629                    par_rot,
2630                    (ParticleKey *)child,
2631                    part->childflat,
2632                    part->childrad);
2633     }
2634
2635     child->time = (float)k / (float)ctx->segments;
2636   }
2637
2638   /* apply effectors */
2639   if (part->flag & PART_CHILD_EFFECT) {
2640     for (k = 0, child = child_keys; k <= ctx->segments; k++, child++) {
2641       if (k) {
2642         do_path_effectors(&ctx->sim,
2643                           cpa->pa[0],
2644                           child,
2645                           k,
2646                           ctx->segments,
2647                           child_keys->co,
2648                           ptex.effector,
2649                           0.0f,
2650                           ctx->cfra,
2651                           &eff_length,
2652                           eff_vec);
2653       }
2654       else {
2655         sub_v3_v3v3(eff_vec, (child + 1)->co, child->co);
2656         eff_length = len_v3(eff_vec);
2657       }
2658     }
2659   }
2660
2661   {
2662     ParticleData *pa = NULL;
2663     ParticleCacheKey *par = NULL;
2664     float par_co[3];
2665     float par_orco[3];
2666
2667     if (ctx->totparent) {
2668       if (i >= ctx->totparent) {
2669         pa = &psys->particles[cpa->parent];
2670         /* this is now threadsafe, virtual parents are calculated before rest of children */
2671         BLI_assert(cpa->parent < psys->totchildcache);
2672         par = cache[cpa->parent];
2673       }
2674     }
2675     else if (cpa->parent >= 0) {
2676       pa = &psys->particles[cpa->parent];
2677       par = pcache[cpa->parent];
2678
2679       /* If particle is unexisting, try to pick a viable parent from particles used for interpolation. */
2680       for (k = 0; k < 4 && pa && (pa->flag & PARS_UNEXIST); k++) {
2681         if (cpa->pa[k] >= 0) {
2682           pa = &psys->particles[cpa->pa[k]];
2683           par = pcache[cpa->pa[k]];
2684         }
2685       }
2686
2687       if (pa->flag & PARS_UNEXIST) {
2688         pa = NULL;
2689       }
2690     }
2691
2692     if (pa) {
2693       ListBase modifiers;
2694       BLI_listbase_clear(&modifiers);
2695
2696       psys_particle_on_emitter(ctx->sim.psmd,
2697                                part->from,
2698                                pa->num,
2699                                pa->num_dmcache,
2700                                pa->fuv,
2701                                pa->foffset,
2702                                par_co,
2703                                NULL,
2704                                NULL,
2705                                NULL,
2706                                par_orco);
2707
2708       psys_apply_child_modifiers(
2709           ctx, &modifiers, cpa, &ptex, orco, hairmat, child_keys, par, par_orco);
2710     }
2711     else {
2712       zero_v3(par_orco);
2713     }
2714   }
2715
2716   /* Hide virtual parents */
2717   if (i < ctx->totparent) {
2718     child_keys->segments = -1;
2719   }
2720 }
2721
2722 static void exec_child_path_cache(TaskPool *__restrict UNUSED(pool),
2723                                   void *taskdata,
2724                                   int UNUSED(threadid))
2725 {
2726   ParticleTask *task = taskdata;
2727   ParticleThreadContext *ctx = task->ctx;
2728   ParticleSystem *psys = ctx->sim.psys;
2729   ParticleCacheKey **cache = psys->childcache;
2730   ChildParticle *cpa;
2731   int i;
2732
2733   cpa = psys->child + task->begin;
2734   for (i = task->begin; i < task->end; ++i, ++cpa) {
2735     BLI_assert(i < psys->totchildcache);
2736     psys_thread_create_path(task, cpa, cache[i], i);
2737   }
2738 }
2739
2740 void psys_cache_child_paths(ParticleSimulationData *sim,
2741                             float cfra,
2742                             const bool editupdate,
2743                             const bool use_render_params)
2744 {
2745   TaskScheduler *task_scheduler;
2746   TaskPool *task_pool;
2747   ParticleThreadContext ctx;
2748   ParticleTask *tasks_parent, *tasks_child;
2749   int numtasks_parent, numtasks_child;
2750   int i, totchild, totparent;
2751
2752   if (sim->psys->flag & PSYS_GLOBAL_HAIR) {
2753     return;
2754   }
2755
2756   /* create a task pool for child path tasks */
2757   if (!psys_thread_context_init_path(&ctx, sim, sim->scene, cfra, editupdate, use_render_params)) {
2758     return;
2759   }
2760
2761   task_scheduler = BLI_task_scheduler_get();
2762   task_pool = BLI_task_pool_create(task_scheduler, &ctx);
2763   totchild = ctx.totchild;
2764   totparent = ctx.totparent;
2765
2766   if (editupdate && sim->psys->childcache && totchild == sim->psys->totchildcache) {
2767     /* just overwrite the existing cache */
2768   }
2769   else {
2770     /* clear out old and create new empty path cache */
2771     free_child_path_cache(sim->psys);
2772
2773     sim->psys->childcache = psys_alloc_path_cache_buffers(
2774         &sim->psys->childcachebufs, totchild, ctx.segments + ctx.extra_segments + 1);
2775     sim->psys->totchildcache = totchild;
2776   }
2777
2778   /* cache parent paths */
2779   ctx.parent_pass = 1;
2780   psys_tasks_create(&ctx, 0, totparent, &tasks_parent, &numtasks_parent);
2781   for (i = 0; i < numtasks_parent; ++i) {
2782     ParticleTask *task = &tasks_parent[i];
2783
2784     psys_task_init_path(task, sim);
2785     BLI_task_pool_push(task_pool, exec_child_path_cache, task, false, TASK_PRIORITY_LOW);
2786   }
2787   BLI_task_pool_work_and_wait(task_pool);
2788
2789   /* cache child paths */
2790   ctx.parent_pass = 0;
2791   psys_tasks_create(&ctx, totparent, totchild, &tasks_child, &numtasks_child);
2792   for (i = 0; i < numtasks_child; ++i) {
2793     ParticleTask *task = &tasks_child[i];
2794
2795     psys_task_init_path(task, sim);
2796     BLI_task_pool_push(task_pool, exec_child_path_cache, task, false, TASK_PRIORITY_LOW);
2797   }
2798   BLI_task_pool_work_and_wait(task_pool);
2799
2800   BLI_task_pool_free(task_pool);
2801
2802   psys_tasks_free(tasks_parent, numtasks_parent);
2803   psys_tasks_free(tasks_child, numtasks_child);
2804
2805   psys_thread_context_free(&ctx);
2806 }
2807
2808 /* figure out incremental rotations along path starting from unit quat */
2809 static void cache_key_incremental_rotation(ParticleCacheKey *key0,
2810                                            ParticleCacheKey *key1,
2811                                            ParticleCacheKey *key2,
2812                                            float *prev_tangent,
2813                                            int i)
2814 {
2815   float cosangle, angle, tangent[3], normal[3], q[4];
2816
2817   switch (i) {
2818     case 0:
2819       /* start from second key */
2820       break;
2821     case 1:
2822       /* calculate initial tangent for incremental rotations */
2823       sub_v3_v3v3(prev_tangent, key0->co, key1->co);
2824       normalize_v3(prev_tangent);
2825       unit_qt(key1->rot);
2826       break;
2827     default:
2828       sub_v3_v3v3(tangent, key0->co, key1->co);
2829       normalize_v3(tangent);
2830
2831       cosangle = dot_v3v3(tangent, prev_tangent);
2832
2833       /* note we do the comparison on cosangle instead of
2834        * angle, since floating point accuracy makes it give
2835        * different results across platforms */
2836       if (cosangle > 0.999999f) {
2837         copy_v4_v4(key1->rot, key2->rot);
2838       }
2839       else {
2840         angle = saacos(cosangle);
2841         cross_v3_v3v3(normal, prev_tangent, tangent);
2842         axis_angle_to_quat(q, normal, angle);
2843         mul_qt_qtqt(key1->rot, q, key2->rot);
2844       }
2845
2846       copy_v3_v3(prev_tangent, tangent);
2847   }
2848 }
2849
2850 /**
2851  * Calculates paths ready for drawing/rendering
2852  * - Useful for making use of opengl vertex arrays for super fast strand drawing.
2853  * - Makes child strands possible and creates them too into the cache.
2854  * - Cached path data is also used to determine cut position for the editmode tool. */
2855 void psys_cache_paths(ParticleSimulationData *sim, float cfra, const bool use_render_params)
2856 {
2857   PARTICLE_PSMD;
2858   ParticleEditSettings *pset = &sim->scene->toolsettings->particle;
2859   ParticleSystem *psys = sim->psys;
2860   ParticleSettings *part = psys->part;
2861   ParticleCacheKey *ca, **cache;
2862
2863   Mesh *hair_mesh = (psys->part->type == PART_HAIR && psys->flag & PSYS_HAIR_DYNAMICS) ?
2864                         psys->hair_out_mesh :
2865                         NULL;
2866
2867   ParticleKey result;
2868
2869   Material *ma;
2870   ParticleInterpolationData pind;
2871   ParticleTexture ptex;
2872
2873   PARTICLE_P;
2874
2875   float birthtime = 0.0, dietime = 0.0;
2876   float t, time = 0.0, dfra = 1.0 /* , frs_sec = sim->scene->r.frs_sec*/ /*UNUSED*/;
2877   float col[4] = {0.5f, 0.5f, 0.5f, 1.0f};
2878   float prev_tangent[3] = {0.0f, 0.0f, 0.0f}, hairmat[4][4];
2879   float rotmat[3][3];
2880   int k;
2881   int segments = (int)pow(2.0, (double)((use_render_params) ? part->ren_step : part->draw_step));
2882   int totpart = psys->totpart;
2883   float length, vec[3];
2884   float *vg_effector = NULL;
2885   float *vg_length = NULL, pa_length = 1.0f;
2886   int keyed, baked;
2887
2888   /* we don't have anything valid to create paths from so let's quit here */
2889   if ((psys->flag & PSYS_HAIR_DONE || psys->flag & PSYS_KEYED || psys->pointcache) == 0) {
2890     return;
2891   }
2892
2893   if (psys_in_edit_mode(sim->depsgraph, psys)) {
2894     if ((psys->edit == NULL || pset->flag & PE_DRAW_PART) == 0) {
2895       return;
2896     }
2897   }
2898
2899   keyed = psys->flag & PSYS_KEYED;
2900   baked = psys->pointcache->mem_cache.first && psys->part->type != PART_HAIR;
2901
2902   /* clear out old and create new empty path cache */
2903   psys_free_path_cache(psys, psys->edit);
2904   cache = psys->pathcache = psys_alloc_path_cache_buffers(
2905       &psys->pathcachebufs, totpart, segments + 1);
2906
2907   psys->lattice_deform_data = psys_create_lattice_deform_data(sim);
2908   ma = give_current_material(sim->ob, psys->part->omat);
2909   if (ma && (psys->part->draw_col == PART_DRAW_COL_MAT)) {
2910     copy_v3_v3(col, &ma->r);
2911   }
2912
2913   if ((psys->flag & PSYS_GLOBAL_HAIR) == 0) {
2914     if ((psys->part->flag & PART_CHILD_EFFECT) == 0) {
2915       vg_effector = psys_cache_vgroup(psmd->mesh_final, psys, PSYS_VG_EFFECTOR);
2916     }
2917
2918     if (!psys->totchild) {
2919       vg_length = psys_cache_vgroup(psmd->mesh_final, psys, PSYS_VG_LENGTH);
2920     }
2921   }
2922
2923   /* ensure we have tessfaces to be used for mapping */
2924   if (part->from != PART_FROM_VERT) {
2925     BKE_mesh_tessface_ensure(psmd->mesh_final);
2926   }
2927
2928   /*---first main loop: create all actual particles' paths---*/
2929   LOOP_PARTICLES
2930   {
2931     if (!psys->totchild) {
2932       psys_get_texture(sim, pa, &ptex, PAMAP_LENGTH, 0.f);
2933       pa_length = ptex.length * (1.0f - part->randlength * psys_frand(psys, psys->seed + p));
2934       if (vg_length) {
2935         pa_length *= psys_particle_value_from_verts(psmd->mesh_final, part->from, pa, vg_length);
2936       }
2937     }
2938
2939     pind.keyed = keyed;
2940     pind.cache = baked ? psys->pointcache : NULL;
2941     pind.epoint = NULL;
2942     pind.bspline = (psys->part->flag & PART_HAIR_BSPLINE);
2943     pind.mesh = hair_mesh;
2944
2945     memset(cache[p], 0, sizeof(*cache[p]) * (segments + 1));
2946
2947     cache[p]->segments = segments;
2948
2949     /*--get the first data points--*/
2950     init_particle_interpolation(sim->ob, sim->psys, pa, &pind);
2951
2952     /* hairmat is needed for for non-hair particle too so we get proper rotations */
2953     psys_mat_hair_to_global(sim->ob, psmd->mesh_final, psys->part->from, pa, hairmat);
2954     copy_v3_v3(rotmat[0], hairmat[2]);
2955     copy_v3_v3(rotmat[1], hairmat[1]);
2956     copy_v3_v3(rotmat[2], hairmat[0]);
2957
2958     if (part->draw & PART_ABS_PATH_TIME) {
2959       birthtime = MAX2(pind.birthtime, part->path_start);
2960       dietime = MIN2(pind.dietime, part->path_end);
2961     }
2962     else {
2963       float tb = pind.birthtime;
2964       birthtime = tb + part->path_start * (pind.dietime - tb);
2965       dietime = tb + part->path_end * (pind.dietime - tb);
2966     }
2967
2968     if (birthtime >= dietime) {
2969       cache[p]->segments = -1;
2970       continue;
2971     }
2972
2973     dietime = birthtime + pa_length * (dietime - birthtime);
2974
2975     /*--interpolate actual path from data points--*/
2976     for (k = 0, ca = cache[p]; k <= segments; k++, ca++) {
2977       time = (float)k / (float)segments;
2978       t = birthtime + time * (dietime - birthtime);
2979       result.time = -t;
2980       do_particle_interpolation(psys, p, pa, t, &pind, &result);
2981       copy_v3_v3(ca->co, result.co);
2982
2983       /* dynamic hair is in object space */
2984       /* keyed and baked are already in global space */
2985       if (hair_mesh) {
2986         mul_m4_v3(sim->ob->obmat, ca->co);
2987       }
2988       else if (!keyed && !baked && !(psys->flag & PSYS_GLOBAL_HAIR)) {
2989         mul_m4_v3(hairmat, ca->co);
2990       }
2991
2992       copy_v3_v3(ca->col, col);
2993     }
2994
2995     if (part->type == PART_HAIR) {
2996       HairKey *hkey;
2997
2998       for (k = 0, hkey = pa->hair; k < pa->totkey; ++k, ++hkey) {
2999         mul_v3_m4v3(hkey->world_co, hairmat, hkey->co);
3000       }
3001     }
3002
3003     /*--modify paths and calculate rotation & velocity--*/
3004
3005     if (!(psys->flag & PSYS_GLOBAL_HAIR)) {
3006       /* apply effectors */
3007       if ((psys->part->flag & PART_CHILD_EFFECT) == 0) {
3008         float effector = 1.0f;
3009         if (vg_effector) {
3010           effector *= psys_particle_value_from_verts(
3011               psmd->mesh_final, psys->part->from, pa, vg_effector);
3012         }
3013
3014         sub_v3_v3v3(vec, (cache[p] + 1)->co, cache[p]->co);
3015         length = len_v3(vec);
3016
3017         for (k = 1, ca = cache[p] + 1; k <= segments; k++, ca++) {
3018           do_path_effectors(
3019               sim, p, ca, k, segments, cache[p]->co, effector, dfra, cfra, &length, vec);
3020         }
3021       }
3022
3023       /* apply guide curves to path data */
3024       if (sim->psys->effectors && (psys->part->flag & PART_CHILD_EFFECT) == 0) {
3025         for (k = 0, ca = cache[p]; k <= segments; k++, ca++) {
3026           /* ca is safe to cast, since only co and vel are used */
3027           do_guides(sim->depsgraph,
3028                     sim->psys->part,
3029                     sim->psys->effectors,
3030                     (ParticleKey *)ca,
3031                     p,
3032                     (float)k / (float)segments);
3033         }
3034       }
3035
3036       /* lattices have to be calculated separately to avoid mixups between effector calculations */
3037       if (psys->lattice_deform_data) {
3038         for (k = 0, ca = cache[p]; k <= segments; k++, ca++) {
3039           calc_latt_deform(psys->lattice_deform_data, ca->co, psys->lattice_strength);
3040         }
3041       }
3042     }
3043
3044     /* finally do rotation & velocity */
3045     for (k = 1, ca = cache[p] + 1; k <= segments; k++, ca++) {
3046       cache_key_incremental_rotation(ca, ca - 1, ca - 2, prev_tangent, k);
3047
3048       if (k == segments) {
3049         copy_qt_qt(ca->rot, (ca - 1)->rot);
3050       }
3051
3052       /* set velocity */
3053       sub_v3_v3v3(ca->vel, ca->co, (ca - 1)->co);
3054
3055       if (k == 1) {
3056         copy_v3_v3((ca - 1)->vel, ca->vel);
3057       }
3058
3059       ca->time = (float)k / (float)segments;
3060     }
3061     /* First rotation is based on emitting face orientation.
3062      * This is way better than having flipping rotations resulting
3063      * from using a global axis as a rotation pole (vec_to_quat()).
3064      * It's not an ideal solution though since it disregards the
3065      * initial tangent, but taking that in to account will allow
3066      * the possibility of flipping again. -jahka
3067      */
3068     mat3_to_quat_is_ok(cache[p]->rot, rotmat);
3069   }
3070
3071   psys->totcached = totpart;
3072
3073   if (psys->lattice_deform_data) {
3074     end_latt_deform(psys->lattice_deform_data);
3075     psys->lattice_deform_data = NULL;
3076   }
3077
3078   if (vg_effector) {
3079     MEM_freeN(vg_effector);
3080   }
3081
3082   if (vg_length) {
3083     MEM_freeN(vg_length);
3084   }
3085 }
3086
3087 typedef struct CacheEditrPathsIterData {
3088   Object *object;
3089   PTCacheEdit *edit;
3090   ParticleSystemModifierData *psmd;
3091   ParticleData *pa;
3092   int segments;
3093   bool use_weight;
3094   float sel_col[3];
3095   float nosel_col[3];
3096 } CacheEditrPathsIterData;
3097
3098 static void psys_cache_edit_paths_iter(void *__restrict iter_data_v,
3099                                        const int iter,
3100                                        const ParallelRangeTLS *__restrict UNUSED(tls))
3101 {
3102   CacheEditrPathsIterData *iter_data = (CacheEditrPathsIterData *)iter_data_v;
3103   PTCacheEdit *edit = iter_data->edit;
3104   PTCacheEditPoint *point = &edit->points[iter];
3105   if (edit->totcached && !(point->flag & PEP_EDIT_RECALC)) {
3106     return;
3107   }
3108   if (point->totkey == 0) {
3109     return;
3110   }
3111   Object *ob = iter_data->object;
3112   ParticleSystem *psys = edit->psys;
3113   ParticleCacheKey **cache = edit->pathcache;
3114   ParticleSystemModifierData *psmd = iter_data->psmd;
3115   ParticleData *pa = iter_data->pa ? iter_data->pa + iter : NULL;
3116   PTCacheEditKey *ekey = point->keys;
3117   const int segments = iter_data->segments;
3118   const bool use_weight = iter_data->use_weight;
3119
3120   float birthtime = 0.0f, dietime = 0.0f;
3121   float hairmat[4][4], rotmat[3][3], prev_tangent[3] = {0.0f, 0.0f, 0.0f};
3122
3123   ParticleInterpolationData pind;
3124   pind.keyed = 0;
3125   pind.cache = NULL;
3126   pind.epoint = point;
3127   pind.bspline = psys ? (psys->part->flag & PART_HAIR_BSPLINE) : 0;
3128   pind.mesh = NULL;
3129
3130   /* should init_particle_interpolation set this ? */
3131   if (use_weight) {
3132     pind.hkey[0] = NULL;
3133     /* pa != NULL since the weight brush is only available for hair */
3134     pind.hkey[0] = pa->hair;
3135     pind.hkey[1] = pa->hair + 1;
3136   }
3137
3138   memset(cache[iter], 0, sizeof(*cache[iter]) * (segments + 1));
3139
3140   cache[iter]->segments = segments;
3141
3142   /*--get the first data points--*/
3143   init_particle_interpolation(ob, psys, pa, &pind);
3144
3145   if (psys) {
3146     psys_mat_hair_to_global(ob, psmd->mesh_final, psys->part->from, pa, hairmat);
3147     copy_v3_v3(rotmat[0], hairmat[2]);
3148     copy_v3_v3(rotmat[1], hairmat[1]);
3149     copy_v3_v3(rotmat[2], hairmat[0]);
3150   }
3151
3152   birthtime = pind.birthtime;
3153   dietime = pind.dietime;
3154
3155   if (birthtime >= dietime) {
3156     cache[iter]->segments = -1;
3157     return;
3158   }
3159
3160   /*--interpolate actual path from data points--*/
3161   ParticleCacheKey *ca;
3162   int k;
3163   float t, time = 0.0f, keytime = 0.0f;
3164   for (k = 0, ca = cache[iter]; k <= segments; k++, ca++) {
3165     time = (float)k / (float)segments;
3166     t = birthtime + time * (dietime - birthtime);
3167     ParticleKey result;
3168     result.time = -t;
3169     do_particle_interpolation(psys, iter, pa, t, &pind, &result);
3170     copy_v3_v3(ca->co, result.co);
3171
3172     /* non-hair points are already in global space */
3173     if (psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
3174       mul_m4_v3(hairmat, ca->co);
3175
3176       if (k) {
3177         cache_key_incremental_rotation(ca, ca - 1, ca - 2, prev_tangent, k);
3178
3179         if (k == segments) {
3180           copy_qt_qt(ca->rot, (ca - 1)->rot);
3181         }
3182
3183         /* set velocity */
3184         sub_v3_v3v3(ca->vel, ca->co, (ca - 1)->co);
3185
3186         if (k == 1) {
3187           copy_v3_v3((ca - 1)->vel, ca->vel);
3188         }
3189       }
3190     }
3191     else {
3192       ca->vel[0] = ca->vel[1] = 0.0f;
3193       ca->vel[2] = 1.0f;
3194     }
3195
3196     /* selection coloring in edit mode */
3197     if (use_weight) {
3198       if (k == 0) {
3199         BKE_defvert_weight_to_rgb(ca->col, pind.hkey[1]->weight);
3200       }
3201       else {
3202         /* warning: copied from 'do_particle_interpolation' (without 'mvert' array stepping) */
3203         float real_t;
3204         if (result.time < 0.0f) {
3205           real_t = -result.time;
3206         }
3207         else {
3208           real_t = pind.hkey[0]->time +
3209                    t * (pind.hkey[0][pa->totkey - 1].time - pind.hkey[0]->time);
3210         }
3211
3212         while (pind.hkey[1]->time < real_t) {
3213           pind.hkey[1]++;
3214         }
3215         pind.hkey[0] = pind.hkey[1] - 1;
3216         /* end copy */
3217
3218         float w1[3], w2[3];
3219         keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
3220
3221         BKE_defvert_weight_to_rgb(w1, pind.hkey[0]->weight);
3222         BKE_defvert_weight_to_rgb(w2, pind.hkey[1]->weight);
3223
3224         interp_v3_v3v3(ca->col, w1, w2, keytime);
3225       }
3226     }
3227     else {
3228       if ((ekey + (pind.ekey[0] - point->keys))->flag & PEK_SELECT) {
3229         if ((ekey + (pind.ekey[1] - point->keys))->flag & PEK_SELECT) {
3230           copy_v3_v3(ca->col, iter_data->sel_col);
3231         }
3232         else {
3233           keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
3234           interp_v3_v3v3(ca->col, iter_data->sel_col, iter_data->nosel_col, keytime);
3235         }
3236       }
3237       else {
3238         if ((ekey + (pind.ekey[1] - point->keys))->flag & PEK_SELECT) {
3239           keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
3240           interp_v3_v3v3(ca->col, iter_data->nosel_col, iter_data->sel_col, keytime);
3241         }
3242         else {
3243           copy_v3_v3(ca->col, iter_data->nosel_col);
3244         }
3245       }
3246     }
3247
3248     ca->time = t;
3249   }
3250   if (psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
3251     /* First rotation is based on emitting face orientation.
3252      * This is way better than having flipping rotations resulting
3253      * from using a global axis as a rotation pole (vec_to_quat()).
3254      * It's not an ideal solution though since it disregards the
3255      * initial tangent, but taking that in to account will allow
3256      * the possibility of flipping again. -jahka
3257      */
3258     mat3_to_quat_is_ok(cache[iter]->rot, rotmat);
3259   }
3260 }
3261
3262 void psys_cache_edit_paths(Depsgraph *depsgraph,
3263                            Scene *scene,
3264                            Object *ob,
3265                            PTCacheEdit *edit,
3266                            float cfra,
3267                            const bool use_render_params)
3268 {
3269   ParticleCacheKey **cache = edit->pathcache;
3270   ParticleEditSettings *pset = &scene->toolsettings->particle;
3271
3272   ParticleSystem *psys = edit->psys;
3273
3274   ParticleData *pa = psys ? psys->particles : NULL;
3275
3276   int segments = 1 << pset->draw_step;
3277   int totpart = edit->totpoint, recalc_set = 0;
3278
3279   segments = MAX2(segments, 4);
3280
3281   if (!cache || edit->totpoint != edit->totcached) {
3282     /* Clear out old and create new empty path cache. */
3283     psys_free_path_cache(edit->psys, edit);
3284     cache = edit->pathcache = psys_alloc_path_cache_buffers(
3285         &edit->pathcachebufs, totpart, segments + 1);
3286     /* Set flag for update (child particles check this too). */
3287     int i;
3288     PTCacheEditPoint *point;
3289     for (i = 0, point = edit->points; i < totpart; i++, point++) {
3290       point->flag |= PEP_EDIT_RECALC;
3291     }
3292     recalc_set = 1;
3293   }
3294
3295   const bool use_weight = (pset->brushtype == PE_BRUSH_WEIGHT) && (psys != NULL) &&
3296                           (psys->particles != NULL);
3297
3298   CacheEditrPathsIterData iter_data;
3299   iter_data.object = ob;
3300   iter_data.edit = edit;
3301   iter_data.psmd = edit->psmd_eval;
3302   iter_data.pa = pa;
3303   iter_data.segments = segments;
3304   iter_data.use_weight = use_weight;
3305
3306   if (use_weight) {
3307     /* use weight painting colors now... */
3308   }
3309   else {
3310     iter_data.sel_col[0] = (float)edit->sel_col[0] / 255.0f;
3311     iter_data.sel_col[1] = (float)edit->sel_col[1] / 255.0f;
3312     iter_data.sel_col[2] = (float)edit->sel_col[2] / 255.0f;
3313     iter_data.nosel_col[0] = (float)edit->nosel_col[0] / 255.0f;
3314     iter_data.nosel_col[1] = (float)edit->nosel_col[1] / 255.0f;
3315     iter_data.nosel_col[2] = (float)edit->nosel_col[2] / 255.0f;
3316   }
3317
3318   ParallelRangeSettings settings;
3319   BLI_parallel_range_settings_defaults(&settings);
3320   settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
3321   BLI_task_parallel_range(0, edit->totpoint, &iter_data, psys_cache_edit_paths_iter, &settings);
3322
3323   edit->totcached = totpart;
3324
3325   if (psys) {
3326     ParticleSimulationData sim = {0};
3327     sim.depsgraph = depsgraph;
3328     sim.scene = scene;
3329     sim.ob = ob;
3330     sim.psys = psys;
3331     sim.psmd = edit->psmd_eval;
3332
3333     psys_cache_child_paths(&sim, cfra, true, use_render_params);
3334   }
3335
3336   /* clear recalc flag if set here */
3337   if (recalc_set) {
3338     PTCacheEditPoint *point;
3339     int i;
3340     for (i = 0, point = edit->points; i < totpart; i++, point++) {
3341       point->flag &= ~PEP_EDIT_RECALC;
3342     }
3343   }
3344 }
3345 /************************************************/
3346 /*          Particle Key handling               */
3347 /************************************************/
3348 void copy_particle_key(ParticleKey *to, ParticleKey *from, int time)
3349 {
3350   if (time) {
3351     memcpy(to, from, sizeof(ParticleKey));
3352   }
3353   else {
3354     float to_time = to->time;
3355     memcpy(to, from, sizeof(ParticleKey));
3356     to->time = to_time;
3357   }
3358 }
3359 void psys_get_from_key(ParticleKey *key, float loc[3], float vel[3], float rot[4], float *time)
3360 {
3361   if (loc) {
3362     copy_v3_v3(loc, key->co);
3363   }
3364   if (vel) {
3365     copy_v3_v3(vel, key->vel);
3366   }
3367   if (rot) {
3368     copy_qt_qt(rot, key->rot);
3369   }
3370   if (time) {
3371     *time = key->time;
3372   }
3373 }
3374
3375 static void triatomat(float *v1, float *v2, float *v3, float (*uv)[2], float mat[4][4])
3376 {
3377   float det, w1, w2, d1[2], d2[2];
3378
3379   memset(mat, 0, sizeof(float) * 4 * 4);
3380   mat[3][3] = 1.0f;
3381
3382   /* first axis is the normal */
3383   normal_tri_v3(mat[2], v1, v2, v3);
3384
3385   /* second axis along (1, 0) in uv space */
3386   if (uv) {
3387     d1[0] = uv[1][0] - uv[0][0];
3388     d1[1] = uv[1][1] - uv[0][1];
3389     d2[0] = uv[2][0] - uv[0][0];
3390     d2[1] = uv[2][1] - uv[0][1];
3391
3392     det = d2[0] * d1[1] - d2[1] * d1[0];
3393
3394     if (det != 0.0f) {
3395       det = 1.0f / det;
3396       w1 = -d2[1] * det;
3397       w2 = d1[1] * det;
3398
3399       mat[1][0] = w1 * (v2[0] - v1[0]) + w2 * (v3[0] - v1[0]);
3400       mat[1][1] = w1 * (v2[1] - v1[1]) + w2 * (v3[1] - v1[1]);
3401       mat[1][2] = w1 * (v2[2] - v1[2]) + w2 * (v3[2] - v1[2]);
3402       normalize_v3(mat[1]);
3403     }
3404     else {
3405       mat[1][0] = mat[1][1] = mat[1][2] = 0.0f;
3406     }
3407   }
3408   else {
3409     sub_v3_v3v3(mat[1], v2, v1);
3410     normalize_v3(mat[1]);
3411   }
3412
3413   /* third as a cross product */
3414   cross_v3_v3v3(mat[0], mat[1], mat[2]);
3415 }
3416
3417 static void psys_face_mat(Object *ob, Mesh *mesh, ParticleData *pa, float mat[4][4], int orco)
3418 {
3419   float v[3][3];
3420   MFace *mface;
3421   OrigSpaceFace *osface;
3422   float(*orcodata)[3];
3423
3424   int i = (ELEM(pa->num_dmcache, DMCACHE_ISCHILD, DMCACHE_NOTFOUND)) ? pa->num : pa->num_dmcache;
3425   if (i == -1 || i >= mesh->totface) {
3426     unit_m4(mat);
3427     return;
3428   }
3429
3430   mface = &mesh->mface[i];
3431   osface = CustomData_get(&mesh->fdata, i, CD_ORIGSPACE);
3432
3433   if (orco && (orcodata = CustomData_get_layer(&mesh->vdata, CD_ORCO))) {
3434     copy_v3_v3(v[0], orcodata[mface->v1]);
3435     copy_v3_v3(v[1], orcodata[mface->v2]);
3436     copy_v3_v3(v[2], orcodata[mface->v3]);
3437
3438     /* ugly hack to use non-transformed orcos, since only those
3439      * give symmetric results for mirroring in particle mode */
3440     if (CustomData_get_layer(&mesh->vdata, CD_ORIGINDEX)) {
3441       BKE_mesh_orco_verts_transform(ob->data, v, 3, 1);
3442     }
3443   }
3444   else {
3445     copy_v3_v3(v[0], mesh->mvert[mface->v1].co);
3446     copy_v3_v3(v[1], mesh->mvert[mface->v2].co);
3447     copy_v3_v3(v[2], mesh->mvert[mface->v3].co);
3448   }
3449
3450   triatomat(v[0], v[1], v[2], (osface) ? osface->uv : NULL, mat);
3451 }
3452
3453 void psys_mat_hair_to_object(
3454     Object *UNUSED(ob), Mesh *mesh, short from, ParticleData *pa, float hairmat[4][4])
3455 {
3456   float vec[3];
3457
3458   /* can happen when called from a different object's modifier */
3459   if (!mesh) {
3460     unit_m4(hairmat);
3461     return;
3462   }
3463
3464   psys_face_mat(0, mesh, pa, hairmat, 0);
3465   psys_particle_on_dm(mesh, from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, vec, 0, 0, 0, 0);
3466   copy_v3_v3(hairmat[3], vec);
3467 }
3468
3469 void psys_mat_hair_to_orco(
3470     Object *ob, Mesh *mesh, short from, ParticleData *pa, float hairmat[4][4])
3471 {
3472   float vec[3], orco[3];
3473
3474   psys_face_mat(ob, mesh, pa, hairmat, 1);
3475   psys_particle_on_dm(
3476       mesh, from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, vec, 0, 0, 0, orco);
3477
3478   /* see psys_face_mat for why this function is called */
3479   if (CustomData_get_layer(&mesh->vdata, CD_ORIGINDEX)) {
3480     BKE_mesh_orco_verts_transform(ob->data, &orco, 1, 1);
3481   }
3482   copy_v3_v3(hairmat[3], orco);
3483 }
3484
3485 void psys_vec_rot_to_face(Mesh *mesh, ParticleData *pa, float vec[3])
3486 {
3487   float mat[4][4];
3488
3489   psys_face_mat(0, mesh, pa, mat, 0);
3490   transpose_m4(mat); /* cheap inverse for rotation matrix */
3491   mul_mat3_m4_v3(mat, vec);
3492 }
3493
3494 void psys_mat_hair_to_global(
3495     Object *ob, Mesh *mesh, short from, ParticleData *pa, float hairmat[4][4])
3496 {
3497   float facemat[4][4];
3498
3499   psys_mat_hair_to_object(ob, mesh, from, pa, facemat);
3500
3501   mul_m4_m4m4(hairmat, ob->obmat, facemat);
3502 }
3503
3504 /************************************************/
3505 /*          ParticleSettings handling           */
3506 /************************************************/
3507 ModifierData *object_add_particle_system(Main *bmain, Scene *scene, Object *ob, const char *name)
3508 {
3509   ParticleSystem *psys;
3510   ModifierData *md;
3511   ParticleSystemModifierData *psmd;
3512
3513   if (!ob || ob->type != OB_MESH) {
3514     return NULL;
3515   }
3516
3517   if (name == NULL) {
3518     name = DATA_("ParticleSettings");
3519   }
3520
3521   psys = ob->particlesystem.first;
3522   for (; psys; psys = psys->next) {
3523     psys->flag &= ~PSYS_CURRENT;
3524   }
3525
3526   psys = MEM_callocN(sizeof(ParticleSystem), "particle_system");
3527   psys->pointcache = BKE_ptcache_add(&psys->ptcaches);
3528   BLI_addtail(&ob->particlesystem, psys);
3529   psys_unique_name(ob, psys, name);
3530
3531   psys->part = BKE_particlesettings_add(bmain, psys->name);
3532
3533   md = modifier_new(eModifierType_ParticleSystem);
3534   BLI_strncpy(md->name, psys->name, sizeof(md->name));
3535   modifier_unique_name(&ob->modifiers, md);
3536
3537   psmd = (ParticleSystemModifierData *)md;
3538   psmd->psys = psys;
3539   BLI_addtail(&ob->modifiers, md);
3540
3541   psys->totpart = 0;
3542   psys->flag = PSYS_CURRENT;
3543   psys->cfra = BKE_scene_frame_get_from_ctime(scene, CFRA + 1);
3544
3545   DEG_relations_tag_update(bmain);
3546   DEG_id_tag_update(&ob->id, ID_RECALC_GEOMETRY);
3547
3548   return md;
3549 }
3550 void object_remove_particle_system(Main *bmain, Scene *UNUSED(scene), Object *ob)
3551 {
3552   ParticleSystem *psys = psys_get_current(ob);
3553   ParticleSystemModifierData *psmd;
3554   ModifierData *md;
3555
3556   if (!psys) {
3557     return;
3558   }
3559
3560   /* clear all other appearances of this pointer (like on smoke flow modifier) */
3561   if ((md = modifiers_findByType(ob, eModifierType_Smoke))) {
3562     SmokeModifierData *smd = (SmokeModifierData *)md;
3563     if ((smd->type == MOD_SMOKE_TYPE_FLOW) && smd->flow && smd->flow->psys) {
3564       if (smd->flow->psys == psys) {
3565         smd->flow->psys = NULL;
3566       }
3567     }
3568   }
3569
3570   if ((md = modifiers_findByType(ob, eModifierType_DynamicPaint))) {
3571     DynamicPaintModifierData *pmd = (DynamicPaintModifierData *)md;
3572     if (pmd->brush && pmd->brush->psys) {
3573       if (pmd->brush->psys == psys) {
3574         pmd->brush->psys = NULL;
3575       }
3576     }
3577   }
3578
3579   /* clear modifier */
3580   psmd = psys_get_modifier(ob, psys);
3581   BLI_remlink(&ob->modifiers, psmd);
3582   modifier_free((ModifierData *)psmd);
3583
3584   /* clear particle system */
3585   BLI_remlink(&ob->particlesystem, psys);
3586   if (psys->part) {
3587     id_us_min(&psys->part->id);
3588   }
3589   psys_free(ob, psys);
3590
3591   if (ob->particlesystem.first) {
3592     ((ParticleSystem *)ob->particlesystem.first)->flag |= PSYS_CURRENT;
3593   }
3594   else {
3595     ob->mode &= ~OB_MODE_PARTICLE_EDIT;
3596   }
3597
3598   DEG_relations_tag_update(bmain);
3599   DEG_id_tag_update(&ob->id, ID_RECALC_GEOMETRY);
3600
3601   /* Flush object mode. */
3602   DEG_id_tag_update(&ob->id, ID_RECALC_COPY_ON_WRITE);
3603 }
3604
3605 static void default_particle_settings(ParticleSettings *part)
3606 {
3607   part->type = PART_EMITTER;
3608   part->distr = PART_DISTR_JIT;
3609   part->draw_as = PART_DRAW_REND;
3610   part->ren_as = PART_DRAW_HALO;
3611   part->bb_uv_split = 1;
3612   part->flag = PART_EDISTR | PART_TRAND | PART_HIDE_ADVANCED_HAIR;
3613
3614   part->sta = 1.0;
3615   part->end = 200.0;
3616   part->lifetime = 50.0;
3617   part->jitfac = 1.0;
3618   part->totpart = 1000;
3619   part->grid_res = 10;
3620   part->timetweak = 1.0;
3621   part->courant_target = 0.2;
3622
3623   part->integrator = PART_INT_MIDPOINT;
3624   part->phystype = PART_PHYS_NEWTON;
3625   part->hair_step = 5;
3626   part->keys_step = 5;
3627   part->draw_step = 2;
3628   part->ren_step = 3;
3629   part->adapt_angle = 5;
3630   part->adapt_pix = 3;
3631   part->kink_axis = 2;
3632   part->kink_amp_clump = 1.f;
3633   part->kink_extra_steps = 4;
3634   part->clump_noise_size = 1.0f;
3635   part->reactevent = PART_EVENT_DEATH;
3636   part->disp = 100;
3637   part->from = PART_FROM_FACE;
3638
3639   part->normfac = 1.0f;
3640
3641   part->mass = 1.0;
3642   part->size = 0.05;
3643   part->childsize = 1.0;
3644
3645   part->rotmode = PART_ROT_VEL;
3646   part->avemode = PART_AVE_VELOCITY;
3647
3648   part->child_nbr = 10;
3649   part->ren_child_nbr = 100;
3650   part->childrad = 0.2f;
3651   part->childflat = 0.0f;
3652   part->clumppow = 0.0f;
3653   part->kink_amp = 0.2f;
3654   part->kink_freq = 2.0;
3655
3656   part->rough1_size = 1.0;
3657   part->rough2_size = 1.0;
3658   part->rough_end_shape = 1.0;
3659
3660   part->clength = 1.0f;
3661   part->clength_thres = 0.0f;
3662
3663   part->draw = 0;
3664   part->draw_line[0] = 0.5;
3665   part->path_start = 0.0f;
3666   part->path_end = 1.0f;
3667
3668   part->bb_size[0] = part->bb_size[1] = 1.0f;
3669
3670   part->keyed_loops = 1;
3671
3672   part->color_vec_max = 1.f;
3673   part->draw_col = PART_DRAW_COL_MAT;
3674
3675   if (!part->effector_weights) {
3676     part->effector_weights = BKE_effector_add_weights(NULL);
3677   }
3678
3679   part->omat = 1;
3680   part->use_modifier_stack = false;
3681   part->draw_size = 0.1f;
3682
3683   part->shape_flag = PART_SHAPE_CLOSE_TIP;
3684   part->shape = 0.0f;