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