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