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