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