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