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